-
Notifications
You must be signed in to change notification settings - Fork 2
/
Backend To-Do.txt
202 lines (165 loc) · 8.32 KB
/
Backend To-Do.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
---- Initial Preparation and Scaffolding ---- DONE ----
-> Opcode (Done)
-> InstructionBuilder (Done)
-> VM Scaffolding: Registers data structure, basic methods such as run() (Done)
---- Implementation of Int/Double/Bool and related functionalities ---- DONE ----
-> Implement basic binary operations on integers and doubles: + - * / % (Done)
-> Implement comparisons & logic operators (Done)
---- Implementation of control flow ---- DONE ----
-> Declare opcodes (Done)
-> Implement (Done)
-> Test (Done)
---- Implementation of casting opcodes ----
-> Declare opcodes (Done)
-> Implement (Done)
-> Test (Done)
---- Implementation of basic CodeGen ----
-> Scaffolding (Done)
-> InstructionBuilder's buffer can be taken (Done)
-> Bytecode Dumper (Done)
-> RegisterAllocator & RegisterValue (Done)
-> Basic CodeGen of simple integral expressions (only ints, bool and char) (Done)
-> VMModule (Done)
-> Scaffoldign of BCGen entry points (Done)
-> Codegen of local variables (Done)
-> Code review in Register.hpp/.cpp and BCGenDecl (Done)
-> BCModule::instr_iterator (Done)
-> BCBuilder Update (Done)
-> Add index when dumping instructions, e.g. [42] StoreSmallInt 3 50 (Done)
-> BCModule/BCModuleBuilder rework part 1(Done)
-> CodeGen of Statements except ReturnStmt (Done)
> BCModule/BCModuleBuilder rework part 2 : Functions (Done)
-> Constants & Constant Table
-> BCModule (Done)
-> BCGen (Done)
-> Instructions + VM support (Done)
-> BCGen of Double literals & expressions (Done)
-> Destination register for ExprGenerator (Done)
-> BCGen of Assignements (Done)
-> Codegen of functions & return statements
-> RegisterAllocator Support for ParamDecl (Done)
-> BCGen support for ParamDecl: Prologue, DeclRef, etc (Done)
-> BCFunction: PCM (Done)
-> VM Instructions (LoadFunc, Call and CallVoid) (Done)
-> Add unused parameters detection in semantic analysis (Done)
-> RegisterAllocator should ignore unused parameters (Done)
-> FuncDecl::numUsedParams() (Done)
-> BCGen::getBCFunction(FuncDecl*) (Done)
-> CallExpr compilation (Done)
---- Implementation of Builtin Functions ----
-> Basic Scaffolding (done)
-> BuiltinFuncDecl (Done)
-> ASTContext::lookupBuiltin (Done)
-> Name Binding/Sema (Done)
-> VM
-> CallBuiltin (Done)
-> FunctionRef (Done)
-> LoadBuiltin instruction + callFunc handling (Done)
-> BCGen (Done)
-> VM (LoadBuiltin + callFunc update) & unit tests (Done)
-> Review the code I wrote for builtins (Done)
-> Unit test for Ambiguous Builtins (Done)
---- Implementation of Object types ----
Note: At first, objects won't be freed. I'll use a leak-forever allocator (LinearAllocator).
GC will come later when the language is officially "feature-complete", because writing a good, reliable
GC takes time and I'll probably write a better one with the full design of the language implemented.
-> Common "Object" base (Done)
-> Strings
-> StringObject (Done)
-> Finish StringObject's implementation
-> VM instructions (Done)
-> NewString (Done)
-> LoadStringK (Done)
-> Test! (Done)
-> StringLiteralExpr BCGen (Done)
-> Builtins
-> StringObject* support (Done)
-> Add all string builtins that I need
-> toString() for Int, Double, Bool, Char (Done)
-> Compile the 'Concat' BinOp in BCGenExpr
-> string+string (Done)
-> handle chars (change the thunk depending on the type) (Done)
-> Default-init variables based on their type (Done)
-> Implement string interface in full (done)
-> Arrays
-> Scaffolding: use std::vector for now (Done)
-> Operations & Builtins
> Array creation: NewValueArray and NewObjectArray instructions (Done)
> ArrayLiteral compilation (Done)
> Subscripts (Done)
> Array-related builtins (Done)
---- Getting feature-complete (with the current feature set) ----
-> Entry point (Done)
-> Global Variables (Done)
-> Add BCModule/BCFunction .verify() to check invariants:
-> Global Var Init Fns cannot use SetGlobal/GetGlobal and must always end with Ret
-> Both GVI fns and normal fns IDs should match their position in their arrays.
-> Constants shouldn't contain duplicates
-> Runtime error management system for the VM
Goal: Be able to diagnose out of range accesses and divisions by zero easily.
I don't need more advanced diagnostics (e.g. diagnosing a single argument in a builtin call)
for now (and I'll probably never need them unless I add null pointers to Fox, which is probably
not going to happen)
-> BCModule Additions (Done)
-> SourceManager&
-> DiagnosticEngine&
-> DebugInfo (Done)
-> VM additions:
-> Runtime error (core logic) (Done)
-> add a new "runtime error" category of diagnostics?
-> Rewrite the messages for the runtime diagnostics
-> Write runtime diagnostic tests (done)
-> Non-numeric CastExpr BCGen
-> Array casts
-> IntArrayToDoubleArray & DoubleArrayToIntArray (work like IntToDouble/DoubleToInt but take a "num dimension" parameter)
-> Allow the register stack to grow dynamically
-> Add recursion tests
-> Properly diagnose maximum register pressure exceeded + max jump ranges exceeded
> e.g. When the RegisterAllocator runs out of registers, it should call a handler
-> Test/Document as much as possible.
-> Rewrite Wiki
---- Implementing the GC ----
-> Objects should behave like a big linked list
-> Change my VM allocator
-> Options are:
-> new/delete + keep a pointer to the first object of the list
-> LinearAllocator (but more complicated since the GC would need to be a moving one)
-> Make String and Vector trivially destructible (if needed -> if I use LinearAllocator/a custom heap)
-> String: use trailing objects
-> Vector: use a separate "Storage" object (ArrayStorageObject
-> Add TypeBase::isReference() -> true for string, array. ignores LValues too.
-> "ReferenceMap" (Safe points) to track register that contain references.
-> Implemented in the RegisterAllocator.
-> I'll need to track which registers are holding references. The easiest way to do that would be to add a method to
RegisterValue "markAsReference" that marks that Register as holding a reference (only for temporaries).
initVar would deduce that using the variable's type probably.
When allocating a new register, always clear the corresponding bit in the reference map.
-> getReferenceMap()
-> Add storage of Reference Maps in BCFunction
-> Generate Reference Maps when I do stuff that allocates data and may trigger a collection, or when
the function "gives up" control in some way.
-> Instantiating an array or a string, either through a literal or variable declaration
-> Doing a call
-> etc.?
-> Proper call stack in the VM that keeps track of called BCFunctions
-> ObjectVisitor
-> GC: Mark and Sweep with colored objects. Non-generational/non-compacting at first
-> Should be fairly straightforward: when collecting, walk the root set using the reference map as a guide.
-> Color objects
-> Clear all non-visited objects.
---- Other To-Dos ----
-> Implement a Sethi-Ullman -like algorithm to decide the evaluation order
of subexpressions (to make regalloc a bit more efficient)
-> Potentially add a way of skipping 'useless' expressions on a case-by-case
basis.
e.g. don't compile a 'Unary Not -> Unary Not -> Expr', just compile expr.
I need to see if there's more of them and if it'd be worthwhile to implement such
a feature.
-> Add a RegisterAllocator enableLogging option to emit logs about
register allocation, such as "Assignated Register X to Var 'foo' 0xABCDEF"
or, upon death, emit the total of registers used, something like that.
Add a "-log-regalloc" option and use write FileCheck tests based on that option.
-> Properly diagnose out of range jumps in BCGen::StmtGenerator::calculateJumpOffset
-> Same as diagnosing register pressure exceeded -> diagnostic like "'if' statement too complex to be compiled: reduce the amount of code contained inside it"
-> (opt) When we have an assignement with the RHS being an empty array literal, simply
emit something like "arrReset" on the LHS instead of generating a new literal.