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
|
# Chapter 18: Functions
I hardly know where to begin! So many things changed here, mostly as indirect
consequences of supporting functions.
Highlights of the changes:
- Function types, and a rework of the type lattice diagrams.
- A distiguished `null` which can be used for both functions and struct pointers.
- Functions themselves can be parsed and evaluated; recursive functions are supported.
- Function calls are allowed, call sites can link and functions inlined.
- The top-level is now a call to function `main`, and this changed most tests.
- A top-level compile driver, which enforces optimization steps.
- A local scheduler.
- A new evaluator which relies on at least code motion, both global and local.
- A graphic animated viewer for peepholes.
Functions are *not* closures in this chapter; that brings about far more
changes and subtle complexities than sensible for such a large chapter.
## Function Types
```
{ argtype, argtype, ... -> rettype }
```
A leading `{` character denotes the start of a function or function type, then
a list of argument types, and arrow `->` and the return type.
Functions themselves are normal variables and assigned the same way:
`functiontype fcn = function-typed-expr`
and function typed variables can be inferred, so `val` and `var` on the left
hand side is fine.
`val sq = { int x -> x*x; }`
Internally, functions have a `TypeTuple` for the arguments, a return `Type`,
and a *function index* spelled as a `fidx` in the code. Function indices are
unique small dense integers, one per unique function. They will be mapped
1-to-1 to the final code address of the generated function code.
Function pointers can refer to more than one function with the same signature,
and the `TypeFunPtr` tracks this as a bit set with the same tuple for signature
and return.
Function types can be `null` just like references.
Functions cannot return `void`, but they can return `null` and have their
return value ignored. A syntactic sugar for this may be added in the future.
## Functions
Functions themselves using the same syntax with as types, but filled in:
```
{ int x, int y ->
sqrt(x*x+y*y);
}
```
Used in a declaration statement:
```
// TYPE VAR = EXPR
{flt,flt->flt} dist = { flt x, flt y ->
sqrt(x*x+y*y);
}
```
With `var`:
```
var dist = { flt x, flt y -> sqrt(x*x*,y*y); }
```
Functions are called in the usual way:
`dist( 1.2, 2.3 ) // yields 2.59422435`
Functions can have zero arguments, in which case the `->` argument seperator is
optional. This allows any section of code to be "thunked" by wrapping it in
`{}`.
`just5 = { -> 5 } // With arrow`
`just5 = { 5 } // Without arrow`
Called:
`just5() // Returns 5`
Functions are always anonymous. When finally assigned to a variable, they will
pick up the variable name for debugging and display purposes, but this has no
semantics meaning. Here is a function variable referring to more than one
anonymous function; the resulting function either doubles or squares:
`val fcn = arg ? { int x -> x+x; } : { int x -> x*x; };`
`fcn(3) // Prints either 6 or 9, depending on arg`
Functions can be recursive:
```
val fact = { int n ->
n <=1 ? n : n*fact(n-1);
};
return fact(4); // Returns 4! or 24`
```
You can early return as normal out of functions:
```
val find = { int[] xs, int x ->
for( int i=0; i<xs#; i++ )
if( xs[i] == x )
return i;
return -1;
};
return find;
```
Unlike prior chapters, all the `return`s from a single function are gathered
together into a single `ReturnNode` point, and they must all be of the same
general type.
When looking at the returned IR, the `StopNode` now reports one return for each
function, including `main`:
`Stop[ return find; return Phi(Region,int,-1); ]`
### Calls
Calls have the usual syntax: `fcn(3)`. Internally a `CallNode` takes in
Control, Memory, all the normal arguments, and a hidden last argument which is
the function pointer. For calls to named functions this last argument will be
a `ConstantNode` of the named function type, but in general it can be the
result of any function-typed expression.
After a `Call` is a `CallEndNode`, internally abbreviated as `cend`. The
`CallEnd` will take the `Call` as an input, and also every *linked* function:
functions the call-site *knows* it will call. This will be expanded later to
be a conservative approximation to the *Call Graph*, with each `CallEnd`
*linked* to ever function it *may* call; if a function is not linked it can not
be called from here. This requires a global analysis (fast, cheap,
incremental, and global), not in this chapter. So for the moment we only
link exact constant functions.
If a call site is linked to a single function, and that single function is only
called by this one call site (its function pointer is only used here, obvious
from GVN) then the function inlines in the IR.
`CallEnd`s are followed by projections for Control, Memory and the return value.
## CodeGen - The Compile Driver
There is now a top-level compile driver that enforces a phase ordering, and
allows multiple compilations; the Fuzzer uses this to compare various generated
programs. The phases are:
- Parse - Convert program text to Simple IR
- Opto - General optimizations; for now iterate peepholes.
- TypeCheck - Error checking after all types have propagated. This mostly
reports on failed null checks.
- Schedule - Global Code Motion scheduler. After this phase, all nodes belong
in some basic block, with the normal suspect CFGNodes being basic blocks.
- LocalSched - a local scheduler. Its completely naive, except it enforces
some required rules: Phis appear at block heads, branchs at block exits.
There's room in the algorithm for a much more sophisticated list scheduler.
The `Eval2` evaluator requires this information.
- RegAlloc - Not implemented (yet).
Several globals moved from the Parser to CodeGen, and probably several others
ought to move here.
There is a very nice `toString()` here; hovering over the `code` variable in
the debug winow will pretty-print the IR "as if" globally scheduled, and the
code becomes very readable.
## Eval2 - A new Evaluator
There is now a second evaluator that uses the scheduling information to
evaluate in a very straightforward way. Essentially the normal IR nodes are
treated like a special "machine instruction set" with infinite registers, and a
globally correct schedule. This evaluator supports functions and calls (and
recursive calls).
## Graph Visualizer
Run as `make view` or `java JSViewer`, type your program in the text box, click
outside the box and then use the arrow keys to view IR generator both forwards
and backwards.
Nodes are color coded according to type, same as the lattice diagrams. Nodes
are shaped according to node function as well. At the bottom are `ScopeNode`s,
which only exist for the Parser but are actual Nodes and have `use->def` edges
into the IR.
|
