ref: 0c14bdce7f2c20becd103d0c8d0641a038b5d83b
parent: 4f90a4d919cc5862fd3ecbffc62b94b515dda7d3
author: Ori Bernstein <[email protected]>
date: Wed Aug 22 16:28:04 EDT 2012
More documentation.
--- a/doc/compiler.txt
+++ b/doc/compiler.txt
@@ -13,8 +13,9 @@
2.5. Serialization
2.6. Usefiles
3. FLATTENING
- 3.1. Control Flow
- 3.2. Complex Expressions
+ 3.1. Flattening Conditionals
+ 3.2. Flattening Complex Expressions
+ 3.3. Building the Control Flow Graph
4. OPTIMIZATION
4.1. Constant Folding
5. CODE GENERATION
@@ -197,7 +198,8 @@
phase should be made machine independent, and passed as a parameter
a machine description describing known integer and pointer sizes, among
other machine attributes. However, for now, it is machine dependent,
- and lives in 6/simp.c.
+ and lives in 6/simp.c, implemented through the callees of simpnode(),
+ such as simpif(), simploop(), and so on.
The goal of flattening a tree is to take semantically involved constructs
such as looping, and simplify things into something that is easy to
@@ -204,7 +206,7 @@
generate code for, as well as something that is easier to analyze for
optimization.
- 3.1. Control Flow:
+ 3.1. Flattening Conditionals:
All if statements, loops, and other complex constructs are simplified
to jumps and conditional jumps. Loops are generally simplified from
@@ -230,12 +232,17 @@
Boolean expressions are simplified to a location to jump to, as
described in section 8.4 of the Dragon book[1].
- 3.2. Complex Expressions:
+ 3.2. Flattening Complex Expressions:
- Complex expressions such as copying types larger than a single machine
- word, pulling members out of structures, emulated multiplication and
- division for larger integers sizes, and similar operations are reduced
- to trees that are expressible in terms of simple machine operations.
+ Complex expressions such as copying types larger than a single
+ machine word, pulling members out of structures, emulated
+ multiplication and division for larger integers sizes, and similar
+ operations are reduced to trees that are expressible in terms of
+ simple machine operations. This is implemented in lval() and rval()
+ in 6/simp.c, which reduce expressions to lvals (assignable
+ expressions which may appear on the left hand side of an assignemnt)
+ or rvals (value-yeilding expressions which may appear on the right
+ side of an assignment.
By the end of the simplification pass, the following operators should
not be present in the trees:
@@ -246,12 +253,81 @@
Oslbase Osllen Ocast
+ After flattening, all nodes must either be pure, or impure roots.
+ With the exception of assignments to a temporary, no inner nodes
+ may be impure. For example, the following sequence of root nodes
+ is valid, as all impure nodes are either roots, or children of
+ rooted assignments to temporaries:
+
+ Oadd
+ Ovar "temp0"
+ Olit int(123)
+ Oasn
+ Ovar "temp1"
+ Ocall
+ Ovar "func"
+ Ovar "arg1"
+ Ovar "arg2"
+ Ocall
+ Ovar "std.put"
+ Olit "some string\n"
+
+ The following tree is invalid because the Ocall node is impure, but
+ it is not the root node or the direct child of a rooted assignment:
+
+ Oasn
+ Ovar "result"
+ Oadd
+ Ovar "temp0"
+ Oasn
+ Ovar "temp1"
+ Ocall
+ Ovar "somefunc"
+ Ovar "arg0"
+ Ovar "arg1"
+
+ In order to make it valid, it must be transformed to the following
+ form:
+
+ Oasn
+ Ovar "temp1"
+ Ocall
+ Ovar "somefunc"
+ Ovar "arg0"
+ Ovar "arg1"
+ Oasn
+ Ovar "result"
+ Oadd
+ Ovar "temp0"
+ Ovar "temp1"
+
+ Note that Oasn, Oblit, and other assignment nodes may only appear as
+ rooted nodes.
+
+
+ 3.3. Building the Control Flow Graph
+
+ Once everything is simplified to relatively flat trees made of
+ primitve operations, a control flow graph is built. The
+ structureless list is split into basic blocks (sequences of
+ instructions where the control flows straight through), and
+ put into the 'Cfg' data structure defined in opt/opt.h. The
+ fact that each Bb within the Cfg has linear flow makes it easier
+ to reason about the code, and thus generate code and implement
+ optimizations.
+
+ This pass is machine independent, as it looks only at the leaders
+ (ie, labels) and trailers (ie, jumps and conditional jumps) for
+ blocks. There are no machine independent components to this process.
+
4. OPTIMIZATION:
Currently, there is virtually no optimization done on the trees after
- flattening. The only optimization that is done is constant folding.
+ flattening. The only optimization that is done is constant folding. All
+ optimizations currently operate on a per-function basis, and preserve
+ [or are required to update] the control flow graph.
- 4.1. Constant Folding:
+ 4.2. Constant Folding:
Expressions with constant values are simplified algebraically. For
example, the expression 'x*1' is simplified to simply 'x', '0/n' is
@@ -265,8 +341,17 @@
Instruction selection is done via a simple hand written bottom up pass
over the tree. Common patterns such as scaled or offset indexing are
recognized by the patterns, but no attempts at finding an optimal
- tiling are made.
+ tiling are made. This is implemented in 6/isel.c and is very machine
+ specific.
+ The structure of the control flow graph is preserved by the
+ instruction selection transformation, with each basic block in the
+ flattened-node flow graph mirrored by an assembly node in the flow
+ graph. This is because there is no need to make the assembly flow
+ graph different when translating, and it is simpler to simply
+ preserve the structure of the flow graph than to rebuild the
+ structure from scratch.
+
5.2. Register Allocation:
Register allocation is done via the algorithm described in "Iterated
@@ -275,6 +360,9 @@
register classes. This will be done as described in "A generalized
algorithm for graph-coloring register allocation", by Smith, Ramsey,
and Holloway.
+
+ The full description will not be mirrored here, as the papers do a
+ far more thorough job of describing the algorithm than I could.
6: TUTORIAL: ADDING A STATEMENT:
--- a/parse/infer.c
+++ b/parse/infer.c
@@ -662,7 +662,7 @@
settype(st, n, mktyarray(n->line, type(st, n->lit.seqval[0]), mkintlit(n->line, n->lit.nelt)));
}
-static void inferpat(Inferstate *st, Node *n, Node ***bind, size_t *nbind)
+static void inferpat(Inferstate *st, Node *n, Node *val, Node ***bind, size_t *nbind)
{size_t i;
Ucon *uc;
@@ -693,6 +693,7 @@
} else {t = mktyvar(n->line);
s = mkdecl(n->line, n->expr.args[0], t);
+ s->decl.init = val;
settype(st, n, t);
lappend(bind, nbind, s);
}