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:
3 * Copyright (C) 2012 David Anderson
5 * This file is part of JITCraft.
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)
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.
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/.
20 #include "../include/keima.h"
22 #include "RootScopes.h"
23 #include "compiler/CompileContext.h"
25 #include "GlobalRoots.h"
26 #include "Reference.h"
28 #include "Interpreter.h"
31 #include "NativeTable.h"
32 #include "Spaces-inl.h"
38 Ke::Keima::Initialize()
40 SingleThreadedZone = new Zone();
41 if (!SingleThreadedZone || !SingleThreadedZone->initialize())
49 delete SingleThreadedZone;
50 SingleThreadedZone = NULL;
53 Ke::HandleScope::HandleScope()
55 position_(zone_->rootScopes().position()),
56 prev_(*zone_->rootScopes().scope())
58 *zone_->rootScopes().scope() = this;
61 Ke::HandleScope::~HandleScope()
63 zone_->rootScopes().unwind(position_);
64 *zone_->rootScopes().scope() = prev_;
68 Ke::HandleScope::CreateHandle(ke::Object *obj)
73 return ZONE()->rootScopes().make(obj);
76 template <typename From, typename To> static inline To *
77 Open(Ke::Handle<From> from)
79 return *reinterpret_cast<To **>(*from);
82 template <typename From, typename To> static inline To *
85 return *reinterpret_cast<To **>(from);
88 template <typename From, typename To> static inline Ke::Local<To>
91 return Ke::Local<To>(reinterpret_cast<To *>(Ke::HandleScope::CreateHandle(from)));
95 InternalCompile(const char *path)
97 PoolScope poolScope(ZONE()->pool());
98 RootScope roots(ZONE());
99 CompileContext cc(ZONE(), path);
101 TranslationUnit *unit = new (ZONE()->pool()) TranslationUnit();
104 if (!cc.addTranslationUnit(unit))
113 ke::Local<ke::Module> module(ZONE(), CompileFromSource(cc, path, bytes, length));
118 ke::Local<ke::String> pathstr(ZONE(), ke::String::New(ZONE(), path, Heap::Tenure_Old));
122 module->setPath(pathstr);
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)
133 ke::Local<ke::Module> module(ZONE(), InternalCompile(path));
134 return ToLocal<ke::Module, Ke::Module>(module);
138 Ke::Keima::InstallMessageReporter(Ke::IMessageReporter *reporter)
140 ZONE()->installErrorReporter(reporter);
143 class StackFrameIterator : public Ke::IStackFrameIterator
153 virtual bool done() {
157 const char *function() {
158 return iter_.function();
161 const char *source() {
162 return iter_.source();
165 unsigned lineNumber() {
166 return iter_.lineNumber();
174 Ke::IStackFrameIterator *
175 Ke::Keima::NewStackFrameIterator()
177 return new StackFrameIterator();
180 static inline ke::HeapRoot *
181 FromAPI(ke::HeapRoot *from)
183 ke::Address address = reinterpret_cast<ke::Address>(from);
184 address -= offsetof(ke::HeapRoot, obj);
185 return reinterpret_cast<ke::HeapRoot *>(address);
189 Ke::Internals::NewHeapRoot()
191 ke::HeapRoot *root = ke::ZONE()->globalRoots()->create();
195 // Compute an interior pointer, so it looks like a Handle to an object.
196 return reinterpret_cast<ke::HeapRoot *>(&root->obj);
200 Ke::Internals::Destroy(ke::HeapRoot *root)
202 ZONE()->globalRoots()->destroy(FromAPI(root));
206 Ke::Keima::IsInCallStack(Handle<Module> argModule)
208 ke::Local<ke::Module> module(ke::ZONE(), Open<Ke::Module, ke::Module>(argModule));
209 return ZONE()->stack().isInCallStack(module);
213 Ke::Keima::CollectGarbage()
215 ke::ZONE()->heap().reclaim();
219 Ke::Keima::ClearPendingException()
221 ke::ZONE()->clearPendingException();
225 Ke::Module::setNativeIdentity(void *identity)
227 ke::Local<ke::Module> module(ke::ZONE(), Open<Ke::Module, ke::Module>(this));
228 module->setNativeIdentity(identity);
234 ke::Local<ke::String> obj(ke::ZONE(), Open<Ke::String, ke::String>(this));
235 return obj->length();
241 ke::Local<ke::String> obj(ke::ZONE(), Open<Ke::String, ke::String>(this));
245 Ke::Local<Ke::String>
248 ke::Local<ke::Function> fun(ke::ZONE(), Open<Ke::Function, ke::Function>(this));
249 return ToLocal<ke::String, Ke::String>(fun->name());
252 static inline const char *
253 GetInvokeTypeName(Ke::Parameter::Type type)
256 case Ke::Parameter::Array:
258 case Ke::Parameter::CharArray:
260 case Ke::Parameter::Float:
262 case Ke::Parameter::FloatRef:
264 case Ke::Parameter::Int:
266 case Ke::Parameter::IntRef:
274 CheckInvokeType(const Ke::Parameter ¶m, Type *type)
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());
298 CheckInvokeTypes(Ke::Handle<Ke::Function> argFun, const Ke::Parameter *params, unsigned nparams)
300 ke::Local<ke::Function> fun(ke::ZONE(), Open<Ke::Function, ke::Function>(argFun));
302 if (fun->nargs() != nparams)
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)));
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())
320 ke::ZONE()->reportError(Message_CannotInvokeReturnType, GetTypeName(returnType));
328 Ke::Keima::Invoke(Handle<Function> argFun, const Parameter *params, unsigned nparams,
329 bool checkTypes, int *retval)
331 assert(CheckInvokeTypes(argFun, params, nparams));
333 ke::Local<ke::Function> fun(ke::ZONE(), Open<Ke::Function, ke::Function>(argFun));
335 if (fun->nargs() != nparams) {
336 // :TODO: report error
342 if (!ke::ZONE()->stack().pushInvokeFrame(fun, args))
345 if (checkTypes && !CheckInvokeTypes(argFun, params, nparams))
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();
355 case Ke::Parameter::Float:
356 slot.f = params[i].f();
359 case Ke::Parameter::IntRef:
360 if (params[i].writeback()) {
361 slot.ref = Reference::NewStack(ke::ZONE(), params[i].i32p(), Heap::Tenure_Stack);
364 other.i32 = *params[i].i32p();
365 slot.ref = Reference::NewStack(ke::ZONE(), other, Heap::Tenure_Stack);
371 case Ke::Parameter::FloatRef:
372 if (params[i].writeback()) {
373 slot.ref = Reference::NewStack(ke::ZONE(), params[i].fp(), Heap::Tenure_Stack);
376 other.f = *params[i].fp();
377 slot.ref = Reference::NewStack(ke::ZONE(), other, Heap::Tenure_Stack);
383 case Ke::Parameter::Array:
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);
392 Array *array = Array::New1D(ke::ZONE(), map, params[i].length(), Heap::Tenure_Stack);
395 if (params[i].length())
396 memcpy(array->bytes(), params[i].buffer(), params[i].length() * sizeof(int));
401 case Ke::Parameter::CharArray:
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);
410 Array *array = Array::New1D(ke::ZONE(), map, params[i].length(), Heap::Tenure_Stack);
413 if (params[i].length())
414 memcpy(array->bytes(), params[i].buffer(), params[i].length() * sizeof(char));
422 if (!Interpret(ke::ZONE(), NULL, &result))
425 if (fun->type()->returnType()->isVoid())
428 *retval = result.i32;
433 Ke::Keima::BindNative(const char *name, void *address)
435 return ke::ZONE()->nativeTable()->bind(name, address);
439 Ke::Keima::SetPublicFunctionListener(IPublicFunctionListener *listener)
441 ke::ZONE()->setPublicFunctionListener(listener);
445 Zone::registerPublic(ke::Handle<Function> fun)
447 if (!publicFunctionListener_)
450 Ke::Local<Ke::Function> local = ToLocal<ke::Function, Ke::Function>(fun);
451 publicFunctionListener_->registerPublic(local);