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
|
# 第15章: 配列
[English](README.md) | 日本語
[前: 第14章](../chapter14/README.ja.md) |
[次: 第16章](../chapter16/README.ja.md)
この文書は [原文](README.md) の日本語訳です。
# 目次
1. [パーサーの変更](#パーサー)
2. [配列型は TypeStruct](#配列型は-typestruct)
3. [割り当てと部分メモリ](#割り当てと部分メモリ)
4. [新しいアドレス計算](#新しいアドレス計算)
5. [構造体の配置](#構造体の配置)
6. [単純なアドレス計算のピープホール最適化](#単純なアドレス計算のピープホール最適化)
7. [考察](#考察)
ついに配列を導入します。配列にはもっと複雑なアドレス計算が必要なので、Load と Store のアドレス指定を、フィールドの*名前*から実際の*オフセット*へ変更しなければなりません。そのため、この章では構造体フィールドの*配置*も行います。
配列は標準的な `new int[len]` 構文で作り、任意の基本型と、長さを表す任意の整数式を使えます。読み書きも通常の形式で、`Person p = persons[idx];` や `persons[idx] = new Person;` とします。長さには後置の `#`、たとえば `persons#` でアクセスします。
Java と同じく、配列には常に安全性のチェックがあり、実行時チェックに失敗すると評価器はパニックになります。
- 範囲外の添字:
- `ary[-1]`
- `ary[ary#]`
- 不正な長さの配列の作成:
- `new int[-1]; // Negative length`（負の長さ）
- `new int[1<<63]; // Too large`（大きすぎる）
- `new int[3.14]; // Not an integer`（整数ではない）
[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの線形の Git リビジョン履歴で[この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter15)を読むことや、前章との[差分](https://github.com/SeaOfNodes/Simple/compare/linear-chapter14...linear-chapter15)を見ることもできます。
## パーサー
配列をサポートするパーサーの変更は、ごく小さなものです。主な変更は、`type()` のパース時に配列構文を探すことです。`int[]` が有効な型になります。配列は任意の次元を許し、基本型も任意なので、たとえば `Person[][]?` は null である可能性がある `Person` の2次元配列です。
配列は常にゼロ/null の本体で作られるので、暗黙に常に `null` 値を許容します。
新しい配列は、新しいオブジェクトとほぼ同じ構文、`new int[99]` で作ります。長さは必須で、任意の整数式を使えます。たとえば `new int[arg]` は長さ `arg` の整数配列です。多次元配列では最も外側の次元だけを作ります。要素自体はすべて null で、次に低い次元の配列として型付けされます。
配列は暗黙に2つのフィールド、長さと本体を持ちます。長さは割り当て時に設定される読み取り専用フィールドで、後置 `#` 演算子、たとえば `ary#` で参照します。配列の合計を求める例です。
```java
int[] ary = new int[arg];
int sum = 0;
int i = 0;
while( i < ary# ) {
sum = sum + ary[i];
i = i + 1;
}
```
配列には2つの暗黙のフィールドがあるので、基本配列型ごとに2つの一意なエイリアス番号を得ます。したがって `int[]` と `flt[]` の型は決してエイリアスしませんが、すべての `int[]` 型はエイリアスします。また、配列本体へのすべての参照も互いにエイリアスします。このため、ループ内で配列へのロードとストアを混在させると、保守的なコード（最適化なし）になることがあります。一部は後の章で対処できます。単純な1次元ステンシル計算は大幅に最適化できますが、Simple コンパイラは複雑なベクトル化を目標にしていません。
## 配列型は TypeStruct
配列は固有の型を持ちますが、実際には `#` と `[]` という名前のフィールドを持つ `TypeStruct` にすぎません。これらはパーサーでフィールド名として使えないので、ユーザーが配列と混同される独自の構造体を書くことはできません。
これらの `TypeStruct` 配列は、ほかの点では `TypeStruct` とまったく同じように振る舞います。
## 割り当てと部分メモリ
この章でも、第11章の1つの隠れた `$mem` 変数と、遅延的な `BulkMemPhi`/`MemPhi` 分割を維持します。Start は `{ctrl, $mem, arg}` を生成し、Return は `{ctrl, $mem, value}` を消費します。配列の初期化によって New が変わります。別々の初期化 Store の代わりに、New がオブジェクトを割り当ててゼロ化します。
New は `{ctrl, $mem, size}` を消費し、`{ptr, $mem}` だけを生成します。New に制御の結果がないため、ポインタは結果 0 です。メモリ入力と結果は、New 内部の `TypeStruct` のフィールドのエイリアスだけを覆います。これらは `TypeMemPtr` からも得られます。エイリアス番号は識別子であり、射影の添字ではありません。
エイリアス `A` に作用する割り当てについて、パーサーは次を構築します。
```text
input = MemMerge(default: absent, each a in A: before[a])
new = New(ctrl, input, size)
ptr = Proj(new, 0)
after = MemMerge(default: before, each a in A: Proj(new, 1))
```
影響を受けるすべてのエントリは、同じメモリ射影を共有します。入力の MemMerge は部分的です。null のデフォルトは、列挙されていないエイリアスを**覆わない**ことを意味します。出力の集約は、関係のないエイリアスについて前のメモリを保持します。空の構造体は空の部分入力を持ち、メモリ全体を変更しません。
メモリ型は、エイリアスと、そのスライスに格納される値の型を対にするようになります。New を通るエイリアス問い合わせは、流入する内容とフィールドの初期値（整数ゼロ、浮動小数点ゼロ、null）を組み合わせます。問い合わせは集約と割り当てをたどり、キャッシュされた Phi の型で止まり、最適化器の依存関係を記録します。MemPhi は、自分の1つのエイリアスについてこれらの値の型を合流します。エイリアスごとの New 射影も、新しい束の領域も不要です。
New 自身のポインタを使う Load は、初期化された値に畳み込めます。別の New から来たポインタは、割り当てを迂回してそのメモリ入力へ進めます。単にノードが異なるだけでは不十分です。Phi やキャストが、依然として割り当てられたオブジェクトを表す可能性があるためです。配列の長さは後続の Store で設定し、本体は New がゼロ化します。配列アクセスは境界チェックの代理として、既存の制御入力を保持します。
両スケジューラは、MemMerge を通してエイリアスをたどり、New のメモリへの作用を見つけます。MemMerge 自体はメモリを上書きしませんが、割り当て前の読み出しと、既存オブジェクトへの後続の書き込みの順序を隠してはいけません。
## 新しいアドレス計算
配列では添字でアクセスするためのアドレス計算が必要なので、Load と Store にオフセットを計算する方法が必要です。以前の Load と Store は構造体だけを対象にし、内部にフィールド名を持っていました。つまり暗黙のアドレス指定はフィールド名によるもの（文字列検索のようなもの）でした。この章で新たに構造体の*配置*を作り、すべての構造体のフィールドのオフセットを計算します。
Load と Store はフィールド名の代わりに `off` を取るようになり、フィールド名はデバッグ用にだけ含めます。
```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;
}
```
配列の `off` は、通常の配列計算の手順で計算します。
`off = base + (idx << scale)`
配列については要素型からベースと添字を計算し、パーサーがオフセットを構築するのに使います。構造体については配置を使います。
```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));
}
```
## 構造体の配置
この章で新しく導入する構造体の*配置*は、特定のフィールドを格納するメモリブロック内の固定オフセットです。`TypeStruct` でオフセットを計算し、キャッシュします。すべてのフィールド型は `log_size` を持つようになります。フィールドはサイズ順に詰め込み、アラインメント用のパディングを入れ、構造体全体も8の倍数までパディングします。したがって実際のフィールドオフセットとフィールドの宣言順序は*無関係*です。大きなフィールドを低い位置に詰め、小さなフィールドをその次に詰めます。
```java
struct s {
i8 b; // log_size=0
u16 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
u16 char; // offset=12, log_size=1
i8 b; // offset=14, log_size=0
void pad; // offset=15, size = 1
} // size =16
```
フィールドのサイズは、おそらく `TypeInteger` を除けばほぼ明らかです。浮動小数点は32ビットか64ビットです。ポインタは `TypeMemPtr` で4バイトに設定しており、後により広いポインタ範囲をサポートするため変更できます。`TypeInteger` は、ユーザーに見える固定された整数範囲の集合についてだけ、有効な `log_size` フィールドを持ちます。Simple では `compute` の呼び出しでほかの範囲も可能ですが、フィールドの基本型には決して現れません。
`struct S { i16 x; }`
ここでは `x` のオフセットは 0、サイズは2バイトで、`S` はサイズ 8 までパディングされます。
`S s = new S; s.x = 3;`
同じ `x` フィールドが今度は 0 または 3 を保持するため、`x` の `TypeInteger` は範囲 `[0-3]` になります。これはたった2ビットで表せますが、フィールドサイズの計算には使いません。
## 単純なアドレス計算のピープホール最適化
0 だけの左シフトは恒等操作です。`(x<<0)` は `x` になります。
定数加算に対する左シフトは分配して、さらに定数畳み込みを可能にします。`(x + c) << i` は `(x << i) + (c << i)` になります。
つまり IR は次のようになります。
`x[i]` は `16/*base*/ + (i << 3/*scale*/)` となり、`Load(mem,x,Add(Shl(i,3),16))` になります。
`x[i+1]` は `16/*base*/ + ((i+1) << 3/*scale*/)` となり、`Load(mem,x,Add(Shl(i,3),24))` になります。
`idx+1` の `+1` がベースの計算に畳み込まれる点に注目してください。
また、この形は X86 のアドレッシングモードにぴったりです。
## 考察
テストケースには、単純な移動和とエラトステネスの篩が含まれます。
```java
int i=0;
while( i < ary# ) {
ary[i] = i;
i = i+1;
}
```
ここでは `i++` 演算子と `for` ループがないことが、はっきり見えます。別の構文を想像できます。
```java
for( int i=0; i < ary#; i++ )
ary[i] = i;
```
これは既存のパーサーの上の糖衣構文だけで実現でき、配列をループする構文をずっと明快にできます。ここには多くの選択肢があり、別の章で集中的に扱うべき話題です。
|
