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