src/Zone.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 <stdlib.h>
    20 #include "Zone.h"
    21 #include "StringPool.h"
    22 #include "TypeManager.h"
    23 #include "GlobalRoots.h"
    24 #include "AllocatorPolicies.h"
    25 #include "Array.h"
    26 #include "NativeTable.h"
    27 #include "Spaces-inl.h"
    28 #include "Heap-inl.h"
    29 
    30 using namespace ke;
    31 
    32 Zone *ke::SingleThreadedZone;
    33 
    34 void * const NullAddress::Sentinel = NULL;
    35 
    36 Zone::Zone()
    37   : stack_(thisFromCtor()),
    38     heap_(thisFromCtor()),
    39     types_(NULL),
    40     symbols_(NULL),
    41     globalRoots_(NULL),
    42     lastLocalRoot_(NULL),
    43     specialRoots_(NULL),
    44     hasPendingException_(false),
    45     reporter_(NULL)
    46 {
    47 }
    48 
    49 Zone::~Zone()
    50 {
    51     delete types_;
    52     delete nativeTable_;
    53     delete globalRoots_;
    54     delete symbols_;
    55 }
    56 
    57 bool
    58 Zone::initialize()
    59 {
    60     if (!stack_.initialize())
    61         return false;
    62     if (!heap_.initialize())
    63         return false;
    64 
    65     symbols_ = new StringPool(this);
    66     if (!symbols_ || !symbols_->initialize())
    67         return false;
    68 
    69     globalRoots_ = new GlobalRoots(this);
    70     if (!globalRoots_ || !globalRoots_->initialize())
    71         return false;
    72 
    73     nativeTable_ = new NativeTable(this);
    74     if (!nativeTable_ || !nativeTable_->initialize())
    75         return false;
    76 
    77     maps_[MapKind_Meta] = heap_.metaMap();
    78     if ((maps_[MapKind_Type] = allocateMap(MapKind_Type, sizeof(Map))) == NULL)
    79         return false;
    80     if ((maps_[MapKind_FunctionType] = allocateMap(MapKind_FunctionType, sizeof(Map))) == NULL)
    81         return false;
    82     if ((maps_[MapKind_StructType] = allocateMap(MapKind_StructType, sizeof(Map))) == NULL)
    83         return false;
    84     if ((maps_[MapKind_FixedArray] = allocateMap(MapKind_FixedArray, sizeof(Map))) == NULL)
    85         return false;
    86     if ((maps_[MapKind_ByteArray] = allocateMap(MapKind_ByteArray, sizeof(Map))) == NULL)
    87         return false;
    88     if ((maps_[MapKind_Code] = allocateMap(MapKind_Code, sizeof(Map))) == NULL)
    89         return false;
    90     if ((maps_[MapKind_Reference] = allocateMap(MapKind_Reference, sizeof(Map))) == NULL)
    91         return false;
    92     if ((maps_[MapKind_MetaArray] = allocateMap(MapKind_MetaArray, sizeof(Map))) == NULL)
    93         return false;
    94     if ((maps_[MapKind_MetaStruct] = allocateMap(MapKind_MetaStruct, sizeof(Map))) == NULL)
    95         return false;
    96     if ((maps_[MapKind_MetaEnvironment] = allocateMap(MapKind_MetaEnvironment, sizeof(Map))) == NULL)
    97         return false;
    98     if ((maps_[MapKind_Module] = allocateMap(MapKind_Module, sizeof(Map))) == NULL)
    99         return false;
   100     if ((maps_[MapKind_Function] = allocateMap(MapKind_Function, sizeof(Map))) == NULL)
   101         return false;
   102     if ((maps_[MapKind_String] = allocateMap(MapKind_String, sizeof(Map))) == NULL)
   103         return false;
   104     if ((maps_[MapKind_Native] = allocateMap(MapKind_Native, sizeof(Map))) == NULL)
   105         return false;
   106     if ((maps_[MapKind_Descriptor] = allocateMap(MapKind_Descriptor, sizeof(Map))) == NULL)
   107         return false;
   108     if ((maps_[MapKind_Box] = allocateMap(MapKind_Box, sizeof(Map))) == NULL)
   109         return false;
   110     if ((maps_[MapKind_FreeRegion] = allocateMap(MapKind_FreeRegion, sizeof(Map))) == NULL)
   111         return false;
   112     if ((maps_[MapKind_EnvironmentSlotDescriptorArray] =
   113          allocateMap(MapKind_EnvironmentSlotDescriptorArray, sizeof(Map))) == NULL)
   114     {
   115         return false;
   116     }
   117 
   118     types_ = new TypeManager(this);
   119     if (!types_ || !types_->initialize())
   120         return false;
   121 
   122     // Create the cached array maps for generic arrays. This is for the API
   123     // version of Invoke(), which needs to make arrays very quickly from C++.
   124     {
   125         // Generic "cell" array (contents do not matter, just non-gc things).
   126         Local<Type> type(this, types_->getPrimitive(PrimitiveType_Int32));
   127         if (!type)
   128             return false;
   129 
   130         type = types_->newExternalArray(type);
   131         if (!type)
   132             return false;
   133 
   134         // :TODO:
   135 #if 0
   136         externalGenericArrayMap_ = ArrayMap::Attach(this, type);
   137         if (!externalGenericArrayMap_)
   138             return false;
   139 #endif
   140 
   141         type = types_->getPrimitive(PrimitiveType_Char);
   142         if (!type)
   143             return false;
   144 
   145         type = types_->newExternalArray(type);
   146         if (!type)
   147             return false;
   148 
   149         // :TODO:
   150 #if 0
   151         externalCharArrayMap_ = ArrayMap::Attach(this, type);
   152         if (!externalCharArrayMap_)
   153             return false;
   154 #endif
   155     }
   156 
   157     return true;
   158 }
   159 
   160 Map *
   161 Zone::allocateMap(MapKind kind, size_t bytes, MapKind parent)
   162 {
   163     assert(maps_[parent]);
   164     Map *map = heap_.allocateMap(kind, bytes);
   165     if (!map)
   166         return NULL;
   167     map->init(maps_[parent]);
   168     return map;
   169 }
   170 
   171 void
   172 Zone::accept(VirtualObjectVisitor *visitor)
   173 {
   174     for (unsigned i = 0; i < MapKinds_Total; i++)
   175         visitor->visit(maps_[i].address());
   176     visitor->visit(externalCharArrayMap_.address());
   177     visitor->visit(externalGenericArrayMap_.address());
   178     types()->accept(visitor);
   179 
   180     Local<Object> *local = lastLocalRoot_;
   181     while (local) {
   182         visitor->visit(local->address());
   183         local = local->prev();
   184     }
   185 
   186     globalRoots_->accept(visitor);
   187     rootScopes_.accept(visitor);
   188     nativeTable_->accept(visitor);
   189 
   190     stack_.accept(visitor);
   191 }
   192 
   193 String *
   194 Zone::makeSymbol(const char *str, size_t length)
   195 {
   196     return symbols_->add(str, length);
   197 }
   198 
   199 String *
   200 Zone::makeSymbol(const char *str)
   201 {
   202     return makeSymbol(str, strlen(str));
   203 }
   204 
   205 bool
   206 Zone::hasPendingException()
   207 {
   208     return hasPendingException_;
   209 }
   210 
   211 void
   212 Zone::reportOutOfMemory()
   213 {
   214     
   215 }
   216 
   217 void
   218 Zone::reportError(Message message, ...)
   219 {
   220     va_list ap;
   221     va_start(ap, message);
   222     reportErrorVA(message, ap);
   223     va_end(ap);
   224 }
   225 
   226 #if defined(_MSC_VER)
   227 # define VA_COPY(to, from)  to = from
   228 #else
   229 # define VA_COPY(to, from)  va_copy(to, from)
   230 #endif
   231 
   232 static char *
   233 BuildErrorMessage(const char *format, va_list ap)
   234 {
   235     va_list use;
   236     VA_COPY(use, ap);
   237 
   238     // We over-allocate and zero terminate ahead of time, since LIBCRT's
   239     // version of vsnprintf is screwy.
   240     size_t size = 255;
   241     char *buffer = (char *)calloc(size + 1, 1);
   242     if (!buffer)
   243         return NULL;
   244 
   245     for (;;) {
   246         int r = vsnprintf(buffer, size, format, use);
   247 
   248         if (r > -1 && size_t(r) < size)
   249             return buffer;
   250        
   251 #if defined(_MSC_VER)
   252         if (r < 0)
   253             size *= 2;
   254 #else
   255         if (r > -1)
   256             size = size_t(r) + 1;
   257         else
   258             size *= 2;
   259 #endif
   260 
   261         free(buffer);
   262         if ((buffer = (char *)calloc(size + 1, 1)) == NULL)
   263             return NULL;
   264 
   265         VA_COPY(use, ap);
   266     }
   267 }
   268 
   269 void
   270 Zone::reportErrorVA(Message message, va_list ap)
   271 {
   272     char *report = BuildErrorMessage(Messages[message].format, ap);
   273     if (!report) {
   274         reportOutOfMemory();
   275         return;
   276     }
   277 
   278     if (reporter_) {
   279         // Reporters can re-enter. When we start having actual exception
   280         // objects that can be caught and inspected, this code will have to
   281         // save and restore the exception state.
   282         reporter_->onUncaughtException(report);
   283     }
   284 
   285     hasPendingException_ = true;
   286 
   287     free(report);
   288 }
   289 
   290 void
   291 Zone::beginCompilationErrors(const char *file)
   292 {
   293     if (reporter_)
   294         reporter_->beginCompilationErrors(file);
   295 }
   296 
   297 void
   298 Zone::reportCompilationError(Message message, unsigned line, unsigned col, va_list ap)
   299 {
   300     char *report = BuildErrorMessage(Messages[message].format, ap);
   301     if (!report) {
   302         reportOutOfMemory();
   303         return;
   304     }
   305 
   306     if (reporter_) {
   307         // Reporters can re-enter. When we start having actual exception
   308         // objects that can be caught and inspected, this code will have to
   309         // save and restore the exception state.
   310         reporter_->reportCompilationError(report, line, col);
   311     }
   312 
   313     free(report);
   314 }
   315 
   316 void
   317 Zone::endCompilationErrors()
   318 {
   319     if (reporter_)
   320         reporter_->endCompilationErrors();
   321 }
   322 
   323 void
   324 Zone::installErrorReporter(Ke::IMessageReporter *reporter)
   325 {
   326     reporter_ = reporter;
   327 }
   328 
   329 void
   330 ZoneAllocatorPolicy::reportOutOfMemory()
   331 {
   332     ZONE()->reportOutOfMemory();
   333 }
   334 
   335 void
   336 ZoneAllocatorPolicy::reportAllocationOverflow()
   337 {
   338     ZONE()->reportAllocationOverflow();
   339 }
   340 
   341 void
   342 Zone::reportAllocationOverflow()
   343 {
   344     reportError(Message_AllocationOverflow);
   345 }
   346 
   347 void
   348 Zone::clearPendingException()
   349 {
   350     hasPendingException_ = false;
   351 }
   352 
   353 void
   354 Zone::setPublicFunctionListener(Ke::IPublicFunctionListener *listener)
   355 {
   356     publicFunctionListener_ = listener;
   357 }
   358 
   359 AutoRooted::AutoRooted(Zone *zone)
   360   : zone_(zone),
   361     prev_(*zone->lastSpecialRoot())
   362 {
   363     *zone->lastSpecialRoot() = this;
   364 }
   365 
   366 AutoRooted::~AutoRooted()
   367 {
   368     *zone_->lastSpecialRoot() = prev_;
   369 }