src/compiler/CompileContext.cpp
author David Anderson <dvander@alliedmods.net>
Sat Nov 17 18:41:01 2012 -0800 (2012-11-17)
changeset 195 c1ba166f3fc4
parent 92 src/CompileContext.cpp@e3974e7360e9
child 196 9904633b1dfc
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.
dvander@195
     1
/*
dvander@195
     2
 * Copyright (C) 2012 David Anderson
dvander@195
     3
 *
dvander@195
     4
 * This file is part of JITCraft.
dvander@195
     5
 *
dvander@195
     6
 * JITCraft is free software: you can redistribute it and/or modify it under
dvander@195
     7
 * the terms of the GNU General Public License as published by the Free
dvander@195
     8
 * Software Foundation, either version 3 of the License, or (at your option)
dvander@195
     9
 * any later version.
dvander@195
    10
 * 
dvander@195
    11
 * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
dvander@195
    12
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
dvander@195
    13
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
dvander@195
    14
 *
dvander@195
    15
 * You should have received a copy of the GNU General Public License along with
dvander@195
    16
 * JITCraft. If not, see http://www.gnu.org/licenses/.
dvander@195
    17
 */
dvander@195
    18
#include <stdio.h>
dvander@195
    19
#include "../Zone.h"
dvander@195
    20
#include "../Interpreter.h"
dvander@195
    21
#include "Scanner.h"
dvander@195
    22
#include "CompileContext.h"
dvander@195
    23
#include "Parser.h"
dvander@195
    24
#include "NameBinding.h"
dvander@195
    25
#include "SemanticAnalysis.h"
dvander@195
    26
#include "../Spaces-inl.h"
dvander@195
    27
#include "../Heap-inl.h"
dvander@195
    28
dvander@195
    29
using namespace ke;
dvander@195
    30
dvander@195
    31
CompileContext::CompileContext(Zone *zone, const char *file)
dvander@195
    32
  : zone_(zone),
dvander@195
    33
    failures_(0),
dvander@195
    34
    file_(file)
dvander@195
    35
{
dvander@195
    36
}
dvander@195
    37
dvander@195
    38
CompileContext::~CompileContext()
dvander@195
    39
{
dvander@195
    40
    if (failures_)
dvander@195
    41
        zone_->endCompilationErrors();
dvander@195
    42
}
dvander@195
    43
dvander@195
    44
bool
dvander@195
    45
CompileContext::addTranslationUnit(TranslationUnit *unit)
dvander@195
    46
{
dvander@195
    47
    if (!units_.append(unit))
dvander@195
    48
        return false;
dvander@195
    49
dvander@195
    50
    if (!unparsed_.append(unit))
dvander@195
    51
        return false;
dvander@195
    52
dvander@195
    53
    return true;
dvander@195
    54
}
dvander@195
    55
dvander@195
    56
char *
dvander@195
    57
CompileContext::loadSource(const char *file, size_t *lengthp)
dvander@195
    58
{
dvander@195
    59
    char *bytes = NULL;
dvander@195
    60
    size_t length;
dvander@195
    61
dvander@195
    62
    FILE *fp = fopen(file, "rb");
dvander@195
    63
    if (!fp) {
dvander@195
    64
        reportError(SourcePosition(), Message_CantOpenFile);
dvander@195
    65
        return NULL;
dvander@195
    66
    }
dvander@195
    67
dvander@195
    68
    if (fseek(fp, 0, SEEK_END)) {
dvander@195
    69
        reportError(SourcePosition(), Message_ErrorSeekingFile);
dvander@195
    70
        fclose(fp);
dvander@195
    71
        return NULL;
dvander@195
    72
    }
dvander@195
    73
    long size = ftell(fp);
dvander@195
    74
    if (size < 0) {
dvander@195
    75
        reportError(SourcePosition(), Message_ErrorSeekingFile);
dvander@195
    76
        fclose(fp);
dvander@195
    77
        return NULL;
dvander@195
    78
    }
dvander@195
    79
    rewind(fp);
dvander@195
    80
    length = size_t(size);
dvander@195
    81
    bytes = new char[length + 1];
dvander@195
    82
    if (fread(bytes, 1, length, fp) != length) {
dvander@195
    83
        reportError(SourcePosition(), Message_ErrorReadingFile);
dvander@195
    84
        fclose(fp);
dvander@195
    85
        delete [] bytes;
dvander@195
    86
        return NULL;
dvander@195
    87
    }
dvander@195
    88
    fclose(fp);
dvander@195
    89
dvander@195
    90
    *lengthp = length;
dvander@195
    91
    return bytes;
dvander@195
    92
}
dvander@195
    93
dvander@195
    94
bool
dvander@195
    95
CompileContext::parse(TranslationUnit *unit)
dvander@195
    96
{
dvander@195
    97
    assert(!unit->tree_);
dvander@195
    98
dvander@195
    99
    size_t length;
dvander@195
   100
    char *source = loadSource(unit->path_.c_str(), &length);
dvander@195
   101
    if (!source)
dvander@195
   102
        return false;
dvander@195
   103
dvander@195
   104
    Parser parser(ZONE(), *this, source, length);
dvander@195
   105
    if ((unit->tree_ = parser.parse()) == NULL)
dvander@195
   106
        return false;
dvander@195
   107
dvander@195
   108
    return true;
dvander@195
   109
}
dvander@195
   110
dvander@195
   111
bool
dvander@195
   112
CompileContext::evaluateImports(TranslationUnit *unit)
dvander@195
   113
{
dvander@195
   114
    if (units_.length() > 1)
dvander@195
   115
        return true;
dvander@195
   116
dvander@195
   117
#if 0
dvander@195
   118
    // For now we hardcode this...
dvander@195
   119
    TranslationUnit *u2 = new (ZONE()->pool()) TranslationUnit();
dvander@195
   120
    u2->path_ = "C:\\Users\\dvander\\jitcraft\\jitcraft-2\\src\\Debug\\wizard.sp";
dvander@195
   121
dvander@195
   122
    ImportStatement *stmt = unit->tree()->imports()->at(0)->toImportStatement();
dvander@195
   123
    stmt->setImportSource(u2);
dvander@195
   124
dvander@195
   125
    if (!u2->dependents_.append(unit))
dvander@195
   126
        return false;
dvander@195
   127
dvander@195
   128
    if (!addTranslationUnit(u2))
dvander@195
   129
        return false;
dvander@195
   130
#endif
dvander@195
   131
dvander@195
   132
    return true;
dvander@195
   133
}
dvander@195
   134
dvander@195
   135
bool
dvander@195
   136
CompileContext::propagateFailure()
dvander@195
   137
{
dvander@195
   138
    Vector<TranslationUnit *> worklist;
dvander@195
   139
    for (size_t i = 0; i < units_.length(); i++) {
dvander@195
   140
        if (units_[i]->failed() && !worklist.append(units_[i]))
dvander@195
   141
            return false;
dvander@195
   142
    }
dvander@195
   143
dvander@195
   144
    while (!worklist.empty()) {
dvander@195
   145
        TranslationUnit *unit = worklist.popCopy();
dvander@195
   146
        for (size_t i = 0; i < unit->dependents().length(); i++) {
dvander@195
   147
            TranslationUnit *other = unit->dependents().at(i);
dvander@195
   148
            if (other->failed())
dvander@195
   149
                continue;
dvander@195
   150
dvander@195
   151
            other->failed_ = true;
dvander@195
   152
            if (!worklist.append(other))
dvander@195
   153
                return false;
dvander@195
   154
        }
dvander@195
   155
    }
dvander@195
   156
dvander@195
   157
    return true;
dvander@195
   158
}
dvander@195
   159
dvander@195
   160
bool
dvander@195
   161
CompileContext::compile()
dvander@195
   162
{
dvander@195
   163
    // Phase 1. Parse all modules we're importing. This process may load new
dvander@195
   164
    // modules off disk, and add them to the parse queue.
dvander@195
   165
    while (!unparsed_.empty()) {
dvander@195
   166
        TranslationUnit *unit = unparsed_.popCopy();
dvander@195
   167
dvander@195
   168
        if (!parse(unit))
dvander@195
   169
            unit->failed_ = true;
dvander@195
   170
dvander@195
   171
        if (!evaluateImports(unit))
dvander@195
   172
            unit->failed_ = true;
dvander@195
   173
    }
dvander@195
   174
dvander@195
   175
    // Phase 2. Create scopes and symbol tables for every lexical region with
dvander@195
   176
    // a declaration. This phase excludes declarations created via imports.
dvander@195
   177
    for (size_t i = 0; i < units_.length(); i++) {
dvander@195
   178
        TranslationUnit *unit = units_[i];
dvander@195
   179
        if (unit->failed())
dvander@195
   180
            continue;
dvander@195
   181
dvander@195
   182
        if (!PopulateNamesAndTypes(zone_, *this, unit))
dvander@195
   183
            unit->failed_ = true;
dvander@195
   184
    }
dvander@195
   185
dvander@195
   186
    // Phase 3. Complete imports and bind all names.
dvander@195
   187
    for (size_t i = 0; i < units_.length(); i++) {
dvander@195
   188
        TranslationUnit *unit = units_[i];
dvander@195
   189
        if (unit->failed())
dvander@195
   190
            continue;
dvander@195
   191
dvander@195
   192
        if (!BindNamesAndTypes(zone_, *this, unit))
dvander@195
   193
            unit->failed_ = true;
dvander@195
   194
    }
dvander@195
   195
dvander@195
   196
    // Phase 4. Assign types to every public name in the module.
dvander@195
   197
    for (size_t i = 0; i < units_.length(); i++) {
dvander@195
   198
        TranslationUnit *unit = units_[i];
dvander@195
   199
        if (unit->failed())
dvander@195
   200
            continue;
dvander@195
   201
dvander@195
   202
    }
dvander@195
   203
dvander@195
   204
    // Intermediate phase. Decide which modules we should not perform
dvander@195
   205
    // semantic analysis on.
dvander@195
   206
    if (!propagateFailure())
dvander@195
   207
        return false;
dvander@195
   208
dvander@195
   209
    // Phase 4. Perform full semantic analysis on each module.
dvander@195
   210
    for (size_t i = 0; i < units_.length(); i++) {
dvander@195
   211
        TranslationUnit *unit = units_[i];
dvander@195
   212
        if (unit->failed())
dvander@195
   213
            continue;
dvander@195
   214
dvander@195
   215
  
dvander@195
   216
    }
dvander@195
   217
dvander@195
   218
    // Intermediate phase. Propagate failure from semantic analysis.
dvander@195
   219
    if (!propagateFailure())
dvander@195
   220
        return false;
dvander@195
   221
dvander@195
   222
    // Phase 5. Now we can finally perform bytecode compilation.
dvander@195
   223
    for (size_t i = 0; i < units_.length(); i++) {
dvander@195
   224
        TranslationUnit *unit = units_[i];
dvander@195
   225
        if (unit->failed())
dvander@195
   226
            continue;
dvander@195
   227
dvander@195
   228
        SemanticAnalysis sema(zone_, *this, unit);
dvander@195
   229
        sema.analyze();
dvander@195
   230
    }
dvander@195
   231
dvander@195
   232
    // Phase 6. Run modules.
dvander@195
   233
    for (size_t i = 0; i < units_.length(); i++) {
dvander@195
   234
        TranslationUnit *unit = units_[i];
dvander@195
   235
        if (unit->failed())
dvander@195
   236
            continue;
dvander@195
   237
dvander@195
   238
        InvokeArgs args;
dvander@195
   239
        if (!zone_->stack().pushModuleFrame(unit->module_, args))
dvander@195
   240
            assert(false);
dvander@195
   241
dvander@195
   242
        ke::LocalSlot slot;
dvander@195
   243
        if (!Interpret(zone_, NULL, &slot))
dvander@195
   244
            assert(false);
dvander@195
   245
    }
dvander@195
   246
dvander@195
   247
    return true;
dvander@195
   248
}
dvander@195
   249
dvander@195
   250
void
dvander@195
   251
CompileContext::reportErrorVa(const SourcePosition &pos, Message msg, va_list ap)
dvander@195
   252
{
dvander@195
   253
    if (!failures_)
dvander@195
   254
        zone_->beginCompilationErrors(file_);
dvander@195
   255
dvander@195
   256
    zone_->reportCompilationError(msg, pos.line, pos.col, ap);
dvander@195
   257
dvander@195
   258
    failures_++;
dvander@195
   259
}
dvander@195
   260
dvander@195
   261
void
dvander@195
   262
CompileContext::reportError(const SourcePosition &pos, Message msg, ...)
dvander@195
   263
{
dvander@195
   264
    va_list ap;
dvander@195
   265
    va_start(ap, msg);
dvander@195
   266
    reportErrorVa(pos, msg, ap);
dvander@195
   267
    va_end(ap);
dvander@195
   268
}