summaryrefslogtreecommitdiff
path: root/doc
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2012-08-22 20:28:04 -0400
committerOri Bernstein <ori@eigenstate.org>2012-08-22 20:28:04 -0400
commit24f21ee97806cbc5e79960f164d0ad766e5d15ac (patch)
treed76d747cb99cbed7afc194b846036c73482922b3 /doc
parent68dcb8f1c00c64a51d087ac92a78c58554c5d7e2 (diff)
downloadmc-24f21ee97806cbc5e79960f164d0ad766e5d15ac.tar.gz
More documentation.
Diffstat (limited to 'doc')
-rw-r--r--doc/compiler.txt112
1 files changed, 100 insertions, 12 deletions
diff --git a/doc/compiler.txt b/doc/compiler.txt
index e0763e2..4c025c8 100644
--- a/doc/compiler.txt
+++ b/doc/compiler.txt
@@ -13,8 +13,9 @@ TABLE OF CONTENTS:
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,14 +198,15 @@ TABLE OF CONTENTS:
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
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 @@ TABLE OF CONTENTS:
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 @@ TABLE OF CONTENTS:
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,7 +341,16 @@ TABLE OF CONTENTS:
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:
@@ -276,6 +361,9 @@ TABLE OF CONTENTS:
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:
6.1. Stubbing in the node types: