src/API.cpp
author David Anderson <dvander@alliedmods.net>
Sat Nov 17 18:41:01 2012 -0800 (2012-11-17)
changeset 195 c1ba166f3fc4
parent 188 bab29bcec7fe
child 209 5cbec15fadfe
permissions -rw-r--r--
Massive SemA/BC refactoring to support better type systems. Read on for more.

The previous compiler had a simple pipeline, best outlined as:
(1) Parsing and name binding -> AST
(2) Storage allocation -> AST
(3) Semantic Analysis (SemA) -> AST
(4) Bytecode Compilation (BC) -> Code

This pipeline, unfortunately, had two problems. First, name binding cannot be performed in one pass if we wish to have multi-file support in the form of modules. Name binding must be two-pass.

Second, because SemA was only capable of annotating AST nodes with a single type, most coercion work had to be duplicated in the BC phase, as coercion was not explicit in the SemA output. This made introducing new type rules extremely difficult, and all but precluded concepts like operator overloading (or overloading at all).

This patch rewrites most of Keima's backend. Of interest are the following changes:
(1) CompileContext has been refactored around future multi-file support.
(2) Parsing no longer performs any name binding.
(3) The grammar for type-and-name has been changed from:
(Label | Identifier)? Identifier
to:
Type? Identifier
where:
Type ::= OldType | NewType
OldType ::= Label
NewType ::= Identifier (. NewType)*


Although we do not implement the full production for Type yet, this
distinction is important. A type identifier is now affixed to the AST
as an Expression (right now, always a NameProxy), so it can fully
participate in name binding.

(4) Immediately after parsing, the AST goes through a NamePopulation phase.
This phase creates Scope objects for every scope which declares a name,
and if those names are declaring types or functions, a Symbol is created
and entered into the scope. Symbols entirely replace the old BoundName
classes.

(5) After NamePopulation comes NameBinding. This phase performs three steps:
(a) Links Scope objects together, to form a tree.
(b) Binds any free name to an existing name in the scope chain.
(c) Creates and registers any Symbols for names which have not yet been
added to the scope (for example, local variables).

In accordance, all "allocation" and "binding" concepts have been removed
from Scopes, which are now lightweight container classes.

(6) SemA now generates bytecode for each statement in the AST. Expression
compilation is performed via a separate mechanism called HIR (High-level
Intermediate Representation). To analyze an expression, SemA will walk
the AST, and produce a HIR object for each node. HIR is typed, and SemA
may insert coercion nodes, or even expand an AST node into multiple HIR
nodes. The result of evaluating an expression in SemA is therefore the
the root of a HIR tree, which SemA then sends to the HIRTranslator, which
performs bytecode generation.

As before, SemA still performs full semantic analysis. However, not it
also produces each function's bytecode.

This split allows us to decompose potentially complex semantics into
a more fine-grained, AST-like structure, which can have very simple
code-generation logic. For example, (1.0 + 5) might look like:

HAdd(HFloat(1.0), HConvert(HInteger(5), <Float>))

As part of this decomposition, many opcodes have been removed. Rather than
using typed jumps, we now expand jumps into longer tests. For example:
jge.f <label>
becomes:
ge.f
cvt.f2b
jt <label>

This simplifies the pipeline, and JITs should be able to melt the added
work away.

HIR is not used at a statement level, and HIR does not have any concept
of control-flow.

(7) The old BytecodeCompiler has been removed, as its work is now split
between SemA and HIRTranslator.


In addition, some minor refactorings have taken place:

(1) Opcodes.tbl no longer hardcodes numbers (aaah).
(2) Type has been split into smaller, typed structs.
(3) BytecodeEmitter no longer relies on Pools or RootScopes.
(4) SemA is now responsible for variable/storage allocation.
(5) Native table are now global, rather than per-module. As such, native
declarations now result in a Native object (which still requires a
CALLNATIVE opcode), which is an index into the global table. Natives
must be bound globally. This is in preparation for module support.
(6) Publics are no longer tracked, but rather registered via a global
callback upon module load. This callback can be set by embedders. This
is in preparation for multi-file support.
(7) The BytecodeEmitter now performs Symbol allocations itself, and it
also generates Code objects itself, which removes a good deal of
complexity.

Finally, a test harness has been added. This harness is a python script which finds *.test files, recursively, in the tests folder. For each file it runs the corresponding .sp. The contents of the .test file must match stdout+stderr.
     1 /* vim: set ts=4 sw=4 tw=99 et:
     2  *
     3  * Copyright (C) 2012 David Anderson
     4  *
     5  * This file is part of JITCraft.
     6  *
     7  * JITCraft is free software: you can redistribute it and/or modify it under
     8  * the terms of the GNU General Public License as published by the Free
     9  * Software Foundation, either version 3 of the License, or (at your option)
    10  * any later version.
    11  * 
    12  * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
    13  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    14  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
    15  *
    16  * You should have received a copy of the GNU General Public License along with
    17  * JITCraft. If not, see http://www.gnu.org/licenses/.
    18  */
    19 #include <string.h>
    20 #include "../include/keima.h"
    21 #include "Zone.h"
    22 #include "RootScopes.h"
    23 #include "compiler/CompileContext.h"
    24 #include "Modules.h"
    25 #include "GlobalRoots.h"
    26 #include "Reference.h"
    27 #include "Array.h"
    28 #include "Interpreter.h"
    29 #include "Stack.h"
    30 #include "Strings.h"
    31 #include "NativeTable.h"
    32 #include "Spaces-inl.h"
    33 #include "Heap-inl.h"
    34 
    35 using namespace ke;
    36 
    37 bool
    38 Ke::Keima::Initialize()
    39 {
    40     SingleThreadedZone = new Zone();
    41     if (!SingleThreadedZone || !SingleThreadedZone->initialize())
    42         return false;
    43     return true;
    44 }
    45 
    46 void
    47 Ke::Keima::Shutdown()
    48 {
    49     delete SingleThreadedZone;
    50     SingleThreadedZone = NULL;
    51 }
    52 
    53 Ke::HandleScope::HandleScope()
    54   : zone_(ke::ZONE()),
    55     position_(zone_->rootScopes().position()),
    56     prev_(*zone_->rootScopes().scope())
    57 {
    58     *zone_->rootScopes().scope() = this;
    59 }
    60 
    61 Ke::HandleScope::~HandleScope()
    62 {
    63     zone_->rootScopes().unwind(position_);
    64     *zone_->rootScopes().scope() = prev_;
    65 }
    66 
    67 ke::Object **
    68 Ke::HandleScope::CreateHandle(ke::Object *obj)
    69 {
    70     if (!obj)
    71         return NULL;
    72 
    73     return ZONE()->rootScopes().make(obj);
    74 }
    75 
    76 template <typename From, typename To> static inline To *
    77 Open(Ke::Handle<From> from)
    78 {
    79     return *reinterpret_cast<To **>(*from);
    80 }
    81 
    82 template <typename From, typename To> static inline To *
    83 Open(From *from)
    84 {
    85     return *reinterpret_cast<To **>(from);
    86 }
    87 
    88 template <typename From, typename To> static inline Ke::Local<To>
    89 ToLocal(From *from)
    90 {
    91     return Ke::Local<To>(reinterpret_cast<To *>(Ke::HandleScope::CreateHandle(from)));
    92 }
    93 
    94 ke::Module *
    95 InternalCompile(const char *path)
    96 {
    97     PoolScope poolScope(ZONE()->pool());
    98     RootScope roots(ZONE());
    99     CompileContext cc(ZONE(), path);
   100 
   101     TranslationUnit *unit = new (ZONE()->pool()) TranslationUnit();
   102     unit->path_ = path;
   103 
   104     if (!cc.addTranslationUnit(unit))
   105         return NULL;
   106 
   107     if (!cc.compile())
   108         return NULL;
   109 
   110     return NULL;
   111 
   112 #if 0
   113     ke::Local<ke::Module> module(ZONE(),  CompileFromSource(cc, path, bytes, length));
   114     delete [] bytes;
   115     if (!module)
   116         return NULL;
   117 
   118     ke::Local<ke::String> pathstr(ZONE(), ke::String::New(ZONE(), path, Heap::Tenure_Old));
   119     if (!pathstr)
   120         return NULL;
   121 
   122     module->setPath(pathstr);
   123     return module;
   124 #endif
   125     return NULL;
   126 }
   127 
   128 // This is split out from InternalCompile so the RootScope doesn't conflict
   129 // with making a return handle.
   130 Ke::Local<Ke::Module>
   131 Ke::Compile(const char *path)
   132 {
   133     ke::Local<ke::Module> module(ZONE(), InternalCompile(path));
   134     return ToLocal<ke::Module, Ke::Module>(module);
   135 }
   136 
   137 void
   138 Ke::Keima::InstallMessageReporter(Ke::IMessageReporter *reporter)
   139 {
   140     ZONE()->installErrorReporter(reporter);
   141 }
   142 
   143 class StackFrameIterator : public Ke::IStackFrameIterator
   144 {
   145     StackIter iter_;
   146 
   147   public:
   148     StackFrameIterator()
   149       : iter_(ZONE())
   150     {
   151     }
   152 
   153     virtual bool done() {
   154         return iter_.done();
   155     }
   156 
   157     const char *function() {
   158         return iter_.function();
   159     }
   160 
   161     const char *source() {
   162         return iter_.source();
   163     }
   164 
   165     unsigned lineNumber() {
   166         return iter_.lineNumber();
   167     }
   168 
   169     void prev() {
   170         iter_.prev();
   171     }
   172 };
   173 
   174 Ke::IStackFrameIterator *
   175 Ke::Keima::NewStackFrameIterator()
   176 {
   177     return new StackFrameIterator();
   178 }
   179 
   180 static inline ke::HeapRoot *
   181 FromAPI(ke::HeapRoot *from)
   182 {
   183     ke::Address address = reinterpret_cast<ke::Address>(from);
   184     address -= offsetof(ke::HeapRoot, obj);
   185     return reinterpret_cast<ke::HeapRoot *>(address);
   186 }
   187 
   188 ke::HeapRoot *
   189 Ke::Internals::NewHeapRoot()
   190 {
   191     ke::HeapRoot *root = ke::ZONE()->globalRoots()->create();
   192     if (!root)
   193         return NULL;
   194 
   195     // Compute an interior pointer, so it looks like a Handle to an object.
   196     return reinterpret_cast<ke::HeapRoot *>(&root->obj);
   197 }
   198 
   199 void
   200 Ke::Internals::Destroy(ke::HeapRoot *root)
   201 {
   202     ZONE()->globalRoots()->destroy(FromAPI(root));
   203 }
   204 
   205 bool
   206 Ke::Keima::IsInCallStack(Handle<Module> argModule)
   207 {
   208     ke::Local<ke::Module> module(ke::ZONE(), Open<Ke::Module, ke::Module>(argModule));
   209     return ZONE()->stack().isInCallStack(module);
   210 }
   211 
   212 void
   213 Ke::Keima::CollectGarbage()
   214 {
   215     ke::ZONE()->heap().reclaim();
   216 }
   217 
   218 void
   219 Ke::Keima::ClearPendingException()
   220 {
   221     ke::ZONE()->clearPendingException();
   222 }
   223 
   224 void
   225 Ke::Module::setNativeIdentity(void *identity)
   226 {
   227     ke::Local<ke::Module> module(ke::ZONE(), Open<Ke::Module, ke::Module>(this));
   228     module->setNativeIdentity(identity);
   229 }
   230 
   231 unsigned
   232 Ke::String::length()
   233 {
   234     ke::Local<ke::String> obj(ke::ZONE(), Open<Ke::String, ke::String>(this));
   235     return obj->length();
   236 }
   237 
   238 const char *
   239 Ke::String::chars()
   240 {
   241     ke::Local<ke::String> obj(ke::ZONE(), Open<Ke::String, ke::String>(this));
   242     return obj->chars();
   243 }
   244 
   245 Ke::Local<Ke::String>
   246 Ke::Function::name()
   247 {
   248     ke::Local<ke::Function> fun(ke::ZONE(), Open<Ke::Function, ke::Function>(this));
   249     return ToLocal<ke::String, Ke::String>(fun->name());
   250 }
   251 
   252 static inline const char *
   253 GetInvokeTypeName(Ke::Parameter::Type type)
   254 {
   255     switch (type) {
   256       case Ke::Parameter::Array:
   257         return "array";
   258       case Ke::Parameter::CharArray:
   259         return "String";
   260       case Ke::Parameter::Float:
   261         return "Float";
   262       case Ke::Parameter::FloatRef:
   263         return "&Float";
   264       case Ke::Parameter::Int:
   265         return "int";
   266       case Ke::Parameter::IntRef:
   267         return "&int";
   268       default:
   269         return "<unknown>";
   270     }
   271 }
   272 
   273 static inline bool
   274 CheckInvokeType(const Ke::Parameter &param, Type *type)
   275 {
   276     switch (param.type()) {
   277       case Ke::Parameter::Array:
   278         return type->isArray() &&
   279                type->levels() == 1 &&
   280                (type->contained()->isPrimitive() || type->contained()->isEnum()) &&
   281                (type->contained()->primitive() != PrimitiveType_Char);
   282       case Ke::Parameter::CharArray:
   283         return type->isCharArray();
   284       case Ke::Parameter::Float:
   285         return type->isFloat();
   286       case Ke::Parameter::FloatRef:
   287         return type->isReference() && type->contained()->isFloat();
   288       case Ke::Parameter::Int:
   289         return type->isInt32() || type->isEnum();
   290       case Ke::Parameter::IntRef:
   291        return type->isReference() && (type->contained()->isInt32() || type->contained()->isEnum());
   292       default:
   293         return false;
   294     }
   295 }
   296 
   297 static bool
   298 CheckInvokeTypes(Ke::Handle<Ke::Function> argFun, const Ke::Parameter *params, unsigned nparams)
   299 {
   300     ke::Local<ke::Function> fun(ke::ZONE(), Open<Ke::Function, ke::Function>(argFun));
   301 
   302     if (fun->nargs() != nparams)
   303         return false;
   304 
   305     for (unsigned i = 0; i < nparams; i++) {
   306         if (!CheckInvokeType(params[i], fun->argType(i))) {
   307             ke::ZONE()->reportError(Message_TypeMismatchDuringInvoke,
   308                                     GetInvokeTypeName(params[i].type()),
   309                                     GetTypeName(fun->argType(i)));
   310             return false;
   311         }
   312     }
   313 
   314     // Functions can only return tagged cells, for ISPE1-compatible Invoke().
   315     ke::Local<ke::Type> returnType(ke::ZONE(), fun->type()->returnType());
   316     if (!returnType->isPrimitive() &&
   317         !returnType->isEnum() &&
   318         !returnType->isVoid())
   319     {
   320         ke::ZONE()->reportError(Message_CannotInvokeReturnType, GetTypeName(returnType));
   321         return false;
   322     }
   323 
   324     return true;
   325 }
   326 
   327 bool
   328 Ke::Keima::Invoke(Handle<Function> argFun, const Parameter *params, unsigned nparams,
   329                   bool checkTypes, int *retval)
   330 {
   331     assert(CheckInvokeTypes(argFun, params, nparams));
   332 
   333     ke::Local<ke::Function> fun(ke::ZONE(), Open<Ke::Function, ke::Function>(argFun));
   334 
   335     if (fun->nargs() != nparams) {
   336         // :TODO: report error
   337         assert(false);
   338         return false;
   339     }
   340 
   341     ke::InvokeArgs args;
   342     if (!ke::ZONE()->stack().pushInvokeFrame(fun, args))
   343         return false;
   344 
   345     if (checkTypes && !CheckInvokeTypes(argFun, params, nparams))
   346         return false;
   347 
   348     for (unsigned i = 0; i < nparams; i++) {
   349         ke::LocalSlot &slot = args.arg(i);
   350         switch (params[i].type()) {
   351           case Ke::Parameter::Int:
   352             slot.i32 = params[i].i32();
   353             break;
   354 
   355           case Ke::Parameter::Float:
   356             slot.f = params[i].f();
   357             break;
   358 
   359           case Ke::Parameter::IntRef:
   360             if (params[i].writeback()) {
   361                 slot.ref = Reference::NewStack(ke::ZONE(), params[i].i32p(), Heap::Tenure_Stack);
   362             } else {
   363                 LocalSlot other;
   364                 other.i32 = *params[i].i32p();
   365                 slot.ref = Reference::NewStack(ke::ZONE(), other, Heap::Tenure_Stack);
   366             }
   367             if (!slot.ref)
   368                 return false;
   369             break;
   370 
   371           case Ke::Parameter::FloatRef:
   372             if (params[i].writeback()) {
   373                 slot.ref = Reference::NewStack(ke::ZONE(), params[i].fp(), Heap::Tenure_Stack);
   374             } else {
   375                 LocalSlot other;
   376                 other.f = *params[i].fp();
   377                 slot.ref = Reference::NewStack(ke::ZONE(), other, Heap::Tenure_Stack);
   378             }
   379             if (!slot.ref)
   380                 return false;
   381             break;
   382 
   383           case Ke::Parameter::Array:
   384           {
   385             ke::Local<ke::ArrayMap> map(ke::ZONE(), ke::ZONE()->externalGenericArrayMap());
   386             if (params[i].writeback()) {
   387                 slot.obj = Array::NewExternal(ke::ZONE(), map, params[i].buffer(),
   388                                               params[i].length(), Heap::Tenure_Stack);
   389                 if (!slot.obj)
   390                     return false;
   391             } else {
   392                 Array *array = Array::New1D(ke::ZONE(), map, params[i].length(), Heap::Tenure_Stack);
   393                 if (!slot.obj)
   394                     return false;
   395                 if (params[i].length())
   396                     memcpy(array->bytes(), params[i].buffer(), params[i].length() * sizeof(int));
   397             }
   398             break;
   399           }
   400 
   401           case Ke::Parameter::CharArray:
   402           {
   403             ke::Local<ke::ArrayMap> map(ke::ZONE(), ke::ZONE()->externalCharArrayMap());
   404             if (params[i].writeback()) {
   405                 slot.obj = Array::NewExternal(ke::ZONE(), map, params[i].buffer(),
   406                                               params[i].length(), Heap::Tenure_Stack);
   407                 if (!slot.obj)
   408                     return false;
   409             } else {
   410                 Array *array = Array::New1D(ke::ZONE(), map, params[i].length(), Heap::Tenure_Stack);
   411                 if (!slot.obj)
   412                     return false;
   413                 if (params[i].length())
   414                     memcpy(array->bytes(), params[i].buffer(), params[i].length() * sizeof(char));
   415             }
   416             break;
   417           }
   418         }
   419     }
   420 
   421     LocalSlot result;
   422     if (!Interpret(ke::ZONE(), NULL, &result))
   423         return false;
   424 
   425     if (fun->type()->returnType()->isVoid())
   426         result.i32 = 0;
   427 
   428     *retval = result.i32;
   429     return true;
   430 }
   431 
   432 bool
   433 Ke::Keima::BindNative(const char *name, void *address)
   434 {
   435     return ke::ZONE()->nativeTable()->bind(name, address);
   436 }
   437 
   438 void
   439 Ke::Keima::SetPublicFunctionListener(IPublicFunctionListener *listener)
   440 {
   441     ke::ZONE()->setPublicFunctionListener(listener);
   442 }
   443 
   444 void
   445 Zone::registerPublic(ke::Handle<Function> fun)
   446 {
   447     if (!publicFunctionListener_)
   448         return;
   449 
   450     Ke::Local<Ke::Function> local = ToLocal<ke::Function, Ke::Function>(fun);
   451     publicFunctionListener_->registerPublic(local);
   452 }