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
|
# Chapter 15: Arrays
At long last we introduce arrays! These require more complex addressing math,
which in turn means we need to change how Loads and Stores do addressing -
with true field *offsets* instead of field *names*. This means we also
will do a struct field *layout* in this chapter.
Arrays are created with the standard `new int[len]` syntax, and can be any base
type and any integer expression length. Arrays are read and written in the usual
style: `Person p = persons[idx];` and `persons[idx] = new Person;`. The length
is accessed with post-fix `#`; e.g. `persons#`.
Like Java, arrays are always safety checked, and failing a runtime check
will panic the Evaluator.
- Indexing out of bounds:
- - `ary[-1]`
- - `ary[ary#]`
- Creating an array with a bad length:
- - `new int[-1]; // Negative length`
- - `new int[1<<63]; // Too large`
- - `new int[3.14]; // Not an integer`
## Parser
The Parser changes to support arrays are fairly minimal. The main change is
when parsing a `type()` we look for array syntax: `int[]` is now a valid type.
Any dimension of arrays are allowed, and the base type can be any type so
e.g. `Person[][]?` is a two-dimensional array of `Person`s which might be null.
Arrays are always created with zero/null bodies, so implicitly always allow
`null` values.
We make a new array with much the same syntax as making a new object: `new
int[99][99]`. The length is required and is any integer expression, so
e.g. `int[arg]` is an integer array of length `arg`.
Arrays implicitly have two fields: the length and the body. The length is a
read-only field set when the array is allocated; it is referenced with the
post-fix `#` operator; e.g. `ary#`. Example to sum an array:
```java
int[] ary = new int[arg];
int i = 0;
while( i < ary# ) {
sum = sum + ary[i];
i = i + 1;
}
```
Because arrays have two implicit fields, they get 2 unique alias numbers per
base array type. This means that `int[]` and `flt[]` types never alias, but
all `int[]` types all alias - and all references into an array body all alias
with each other. This can lead to some conservative code (no optimization)
with mixing loads and stores in an array in a loop. Some of this can be
addressed in a later chapter - simple 1-d stencil calculations can be heavily
optimized - but Simple the compiler is not targeting complex vectorization.
## Type Array is TypeStruct
Arrays have a unique type, which is actually just a `TypeStruct` with fields
named `#` and `[]`. Since these are not available as field names from within
the Parser, users cannot write their own structs which get confused as arrays.
These `TypeStruct` arrays otherwise behave exactly as a `TypeStruct`.
## New Address Math
Since arrays need adressing math to index into them, Loads and Stores need a
way to compute an offset. Previously Loads and Stores only worked on structs,
and included the field name within them - thus the impicit addressing was field
name (e.g. a string lookup!). New in this chapter we create a struct *layout*
and compute field offsets to all structs.
Loads and Stores now take an `off` instead of a field name, and the field
name is included for debugging only.
```java
public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) {
super(null, mem, ptr, off);
_name = name;
_alias = alias;
_declaredType = glb;
}
```
For arrays, the `off` is computed via the normal array math sequence:
`off = base + (idx << scale)`
The base and index are computed for arrays from the element type, and used
by the parser to build the offset. For structs, the layout is used.
```java
// Get field type and layout offset from base type and field index fidx
Field f = base._fields[fidx]; // Field from field index
Node off;
if( name.equals("[]") ) { // If field is an array body
// Array index math
Node idx = require(parseExpression(),"]");
off = new AddNode(con(base.aryBase()),new ShlNode(idx,con(base.aryScale())).peephole()).peephole();
} else { // Else normal struct field
// Hardwired field offset
off = con(base.offset(fidx));
}
```
## Struct Layout
New in this chapter is struct *layouts*: a fixed offset inside a block of
memory where a particular field is stored. The offset is computed and cached
in `TypeStruct`. Every field type now has a `log_size`. These fields are
packed by size, with alignment padding and the whole struct is padded out to
mod 8. This means the actual field offset and the field declaration order are
*unrelated*: large fields pack low, and smaller fields pack next.
```java
struct s {
int8 b; // log_size=0
uint16 char; // log_size=1
Person p; // log_size=2
flt pi; // log_size=3
}
// Layout will be:
struct s {
flt pi; // offset= 0, log_size=3
Person p; // offset= 8, log_size=2
uint16 char; // offset=12, log_size=1
int8 b; // offset=13, log_size=0
void pad; // offset=14, size = 2
} // size =16
```
Field size is mostly obvious except perhaps for `TypeInteger`. Floats are
either 32 bits or 64 bits. Pointers are set at 4 bytes in `TypeMemPtr` and
this could be changed at a later date to support a larger range of pointers.
`TypeInteger` only has valid `log_size` fields for a fixed set of user-visible
integer ranges. Other ranges are possible in Simple via `compute` calls, but
these will never show up as base field types:
`struct S { int16 x; }`
Here `x` will have offset 0 and size 2 bytes, and `S` will be padded to size 8.
`S s = new S; s.x = 3;`
The same `x` field now holds either a 0 or a 3, so the `TypeInteger` for `x`
will be a range `[0-3]` which could be represented in just 2 bits ... but this is not used to compute the field size.
## Some Simple Address Math Peeps
Shift-left by 0 is an identity: `(x<<0)` becomes `x`.
Shift-left with a constant add distributes, to allow more constant folding:
`(x + c) << i` becomes `(x << i) + (c << i)`.
This means the IR for:
`x[i]` becomes `16/*base*/ + (i << 3/*scale*/)`
becomes `Load(mem,x,Add(Shl(i,3),16))`
`x[i+1]` becomes `16/*base*/ + ((i+1) << 3/*scale*)` becomes
`Load(mem,x,Add(Shl(i,3),24))`
Notice the `idx+1` folds the `+1` into the base math.
## Discussion
Included in the test cases in a simple rolling sum, and a Sieve of Eratosthenes.
```java
int i=0;
while( i < ary# ) {
ary[i] = i;
i = i+1;
}
```
Here we really see the lack of a `i++` operator and a `for` loop. You can
imagine another syntax:
```java
for( int i=0; i < ary#; i++ )
ary[i] = i;
```
that would be entirely syntatic-sugar over the existing parser, but would
really help make array looping syntax clearer. There are lots of options
here, which should really be the focus of another chapter!
|
