Skip to content

Latest commit

 

History

History
119 lines (85 loc) · 4.53 KB

todo.md

File metadata and controls

119 lines (85 loc) · 4.53 KB
Raw

Status

To Do

  • goto
  • select
  • type checking
  • type assertions and conversions (in progress)
  • type switch
  • interfaces (in progress)
  • diagnostics and proper error handling
  • named output variables (test/ret1.gi)
  • defer
  • ellipsis

Done

  • basic literals
  • variable definition and assignment
  • arithmetic and logical expressions
  • if / else statement, including init
  • for statement
  • go routines
  • channels
  • variables definition (1 scope per function)
  • function definition
  • function calls
  • methods
  • assignements, including to/from multi value
  • return, including multiple values
  • for range
  • arrays
  • maps
  • &&, ||, break, continue
  • switch (partial)
  • type declarations
  • hierarchical scopes for symbol resolution
  • universe (global) scope
  • closures
  • imports from exec
  • imports from source
  • init functions
  • exports to exec
  • pointers, including on struct, method receivers...
  • slices / map expressions
  • variadic functions
  • constants
  • iota
  • forward declarations
  • method calls from runtime to interpreter

Developpement plan

Step 1: a symbolic interpreter

The fisrt step consists to create a symbolic interpreter, generic, architecture independent, with a minimal execution layer on top of the abstract syntax tree (AST).

The lexical and syntaxic analysis are to be reused from Go toolchain code (up to AST production).

The AST (abstract syntax tree) will be extended to permit in place execution through extending the AST to a control flow graph (CFG), using a technique developped for bip (private project), and allowing high speed interpretation on top of AST.

The result of first step is a fully workable and portable Go interpreter with all features present in the language, but with a limited level of performances.

The starting point is the bip interpreter (Marc's private project) in C, ported to Go.

Step 2: an optimizing tracing JIT compiler

The second step consists to add a dynamic code generator, thus extending the interperter with a Just-In-Time compiler.

The dynamic code generator converts parts of the intermediate representation (IR), here a specialy annotated AST, directly to machine code in executable memory pages. It is expected to reuse parts of the Go assembler for the machine code generation).

One idea is to use traces from the interpreter to replace hot paths (i.e. intensive loops) by snippets of stream-lined native code. The code generator doesn't need to be complete to start gaining performance improvemeents, as only parts where code generator is guaranteed to works will be applied, and the symbolic execution level serves as a fallback.

Design notes

This section documents some design analyses and choices. It is related to symbolic interpretation (step 1) only for now.

AST Peculiarities

AST is fundamental to code analysis, various compilation steps and interpretation. It is very important to get it right, specially for a dynamic interpreter.

Limitations of go/ast

The go/ast has been designed and optimized for parsing operations. It relies exclusively on interface methods to perform traversal of the tree (node objects must provide a visitor method).

the AST is a tree structure where nodes are objects of different types (type being specialized according to the kind of object: expression, statement list, operator, identificator, etc.).

In this case, traversal can be performed only recursively, less efficiently than an iterative traversal.

In addition, the provided Walk method implements only depth first traversal in pre-order manner (where node callback is called before visiting children nodes), but it is required to process nodes in post-order (node callback called after visiting all children), at least for CFG generation, optimizations at AST level and code generation.

Our AST

Our AST is represented with a tree of objects of all the same type Node, each node containing pointers to ancestor and children.

This structure allows a simpler implementation of recursive tree walk, and makes possible an faster and more efficient non-recursive tree walk.

The tree walk allows callback both for pre-order and post-order processing.

Example

Consider the following source:

package main

func main() {
	for a := 0; a < 10000; a++ {
		if (a & 0x8ff) == 0x800 {
			println(a)
		}
	}
}

AST: ast

CFG: cfg

In CFG, the node labels correspond to the number in left of AST nodes