Skip to content
← Back

src/syntax/process/pipe_fusion_recognizer.ghul

1
namespace Syntax.Process is
2
use Collections;
3
4
use Semantic;
5
6
// One stage of a recognised pipe chain. Three kinds:
7
//
8
// - map (is_filter false, is_index false): `argument` is the mapper.
9
// - filter (is_filter true): `argument` is the predicate.
10
// - index (is_index true): no argument; the loop keeps a running
11
// counter starting at `index_start` and emits
12
// `INDEXED_VALUE[element](counter, current)` per element.
13
// compile-expressions fills `indexed_value_type` (the constructed
14
// `INDEXED_VALUE[element]` struct) and `indexed_value_constructor`.
15
//
16
// For a map/filter stage whose `argument` is an inlinable literal
17
// lambda, compile-expressions fills `param_local` (a synthetic
18
// enclosing-method local the loop assigns the incoming element to) and
19
// `inline_body` (the lambda body re-walked in the enclosing scope, so
20
// its parameter loads that local and its captures load ordinary
21
// enclosing locals - no delegate, no closure frame). When both are set
22
// the loop emits the body inline; otherwise it invokes the argument's
23
// compiled delegate value.
24
class PIPE_FUSION_STAGE is
25
is_filter: bool public;
26
is_index: bool public;
27
28
// A `take`/`skip` stage: `argument` is the int count expression,
29
// evaluated once into a running counter that the loop decrements per
30
// pulled element (take stops the loop when it runs out; skip drops
31
// the element while it remains).
32
is_take: bool public;
33
is_skip: bool public;
34
35
// The stage's argument: a map/filter lambda or delegate, or the int
36
// count of a take/skip stage. Null for an index stage.
37
argument: Trees.Expressions.Expression? public;
38
39
// Index stage only.
40
index_start: int public;
41
indexed_value_type: Semantic.Types.Type? public;
42
indexed_value_constructor: Semantic.Symbols.Function? public;
43
44
param_local: Semantic.Symbols.Variable? public;
45
inline_body: IR.Values.Value? public;
46
47
// A take/skip stage keeps a running counter but transforms nothing,
48
// so the element passes through unchanged.
49
is_countdown: bool => is_take \/ is_skip;
50
51
is_inlined: bool => param_local? /\ inline_body?;
52
53
// A fusible index stage needs both its type and constructor
54
// resolved; otherwise the recogniser rejects the chain.
55
is_index_ready: bool => indexed_value_type? /\ indexed_value_constructor?;
56
57
init(is_filter: bool, argument: Trees.Expressions.Expression) is
58
self.is_filter = is_filter;
59
self.argument = argument;
60
si
61
62
init(index_start: int) is
63
self.is_index = true;
64
self.index_start = index_start;
65
si
66
67
init(is_take: bool, is_skip: bool, count: Trees.Expressions.Expression) is
68
self.is_take = is_take;
69
self.is_skip = is_skip;
70
self.argument = count;
71
si
72
si
73
74
// Stage-B inlining (`_try_inline_stage` in compile-expressions)
75
// harvests IR straight from a speculative compile-expressions walk of
76
// the stage lambda's body, then splices it directly into the fused
77
// loop - it is never walked again during generate-il. A `cast`
78
// expression compiles in two stages: compile-expressions leaves a
79
// `WRAPPER` placeholder around a poisoning `DUMMY` value, and only
80
// generate-il's own walk (`visit(CAST)`) fills it in with the real
81
// conversion. An inlined stage skips that second walk entirely, so a
82
// `cast` anywhere in its body reaches `gen()` still holding the
83
// placeholder and the compiler dies with "generated dummy value".
84
// Scanning for one disqualifies the stage from inlining; the delegate
85
// fallback compiles the same body as an ordinary function, which does
86
// get generate-il's normal walk.
87
class INLINE_DISQUALIFYING_SCANNER: Visitor is
88
_found: bool;
89
90
init() is
91
super.init();
92
si
93
94
contains_cast(body: Trees.Bodies.Body?) -> bool is
95
_found = false;
96
97
if body? then
98
body.walk(self);
99
fi
100
101
return _found;
102
si
103
104
pre(`cast: Trees.Expressions.CAST) -> bool is
105
_found = true;
106
107
return true;
108
si
109
110
pre(function: Trees.Definitions.FUNCTION) -> bool => true;
111
pre(function: Trees.Expressions.FUNCTION) -> bool => true;
112
si
113
114
// A recognised, provably-sound fusible pipe chain rooted at a `for`
115
// loop. `source` is the pinned iterable fed to the base `pipe(...)`
116
// wrap (see the soundness gate in PIPE_FUSION_RECOGNIZER); the fused
117
// loop iterates it directly - so the wrapping ADAPTOR_PIPE is never
118
// built either - and applies `stages` inline per element. `stages`
119
// are outermost-first (the order they wrap the source), so inline
120
// application walks them in reverse.
121
class PIPE_FUSION(source: Trees.Expressions.Expression, stages_outermost_first: LIST[PIPE_FUSION_STAGE], needs_guard: bool) is
122
source: Trees.Expressions.Expression public;
123
stages_outermost_first: LIST[PIPE_FUSION_STAGE] public;
124
125
// True when the source's dynamic type could be a user Pipe with an
126
// overridden map/filter (any non-sealed source - it is only
127
// statically not a Pipe). The fused loop is then emitted behind a
128
// per-site `if source isa Pipe[elem]` guard that mirrors what
129
// pipe() itself does (pipe.ghul: `elif isa Pipe[T](source)`): guard
130
// true falls back to the ordinary pipe-object loop, guard false
131
// fuses. False for sealed sources (value types, arrays) which
132
// cannot dynamically be a Pipe, so fuse unconditionally.
133
needs_guard: bool public;
134
135
// The source's own iterator members, resolved against its type
136
// exactly as a plain `for x in source` would. read_iterator is
137
// null when the source is directly an iterator (e.g. a range);
138
// otherwise it yields the iterator that move_next / read_current
139
// drive. Filled by compile-expressions after recognition.
140
source_read_iterator: Semantic.Symbols.Function? public;
141
source_move_next: Semantic.Symbols.Function? public;
142
source_read_current: Semantic.Symbols.Function? public;
143
144
// The `Pipe[source-element]` type the runtime guard tests the
145
// source against (`source isa Pipe[T]`). T is the SOURCE's own
146
// element type - the same T `pipe()` uses when it decides whether
147
// to short-circuit - so guard and pipe() always agree. Filled by
148
// compile-expressions only when `needs_guard`.
149
guard_isa_type: Semantic.Types.Type? public;
150
si
151
152
// Decides whether a `for x in <chain>` loop's expression is a
153
// fusible pipe chain, and if so returns the plan the IL pass
154
// consumes. Pure recognition — no compilation side effects.
155
//
156
// Soundness: Pipe[T] is a trait with virtual `map`/`filter`/`index`/
157
// `take`/`skip`, so a user type implementing Pipe may override them.
158
// Static resolution to Pipe.map is not enough — the `callvirt`
159
// dispatches on the receiver's dynamic type. The chain is only fused
160
// when its BASE provably uses the default ops; an induction over the
161
// closed-to-assembly built-in pipe classes then secures every
162
// downstream stage (each stage's receiver is a value freshly produced
163
// by an already-pinned default op returning a closed built-in pipe -
164
// MAP_PIPE / FilterPipe / INDEX_PIPE / TAKE_PIPE / SKIP_PIPE).
165
//
166
// The base must be a `pipe(SOURCE)` wrap (the postfix `|` operator,
167
// carrying `is_pipe_wrap`) whose SOURCE is not itself statically a
168
// Pipe. Two cases:
169
//
170
// - SOURCE is sealed (a value type or an array): its dynamic type is
171
// exactly its static type, so it cannot secretly be a user pipe with
172
// an override. `pipe()` provably wraps it in the built-in (closed)
173
// ADAPTOR_PIPE, and the fused loop skips even that by iterating
174
// SOURCE directly. Fuse unconditionally (`needs_guard` false).
175
//
176
// - SOURCE is any other type (a collection interface, an open class):
177
// it is only *statically* not a Pipe - its dynamic type could be a
178
// user Pipe with an override. Fuse behind a per-site runtime guard
179
// `if SOURCE isa Pipe[elem]` (`needs_guard` true), sound because it
180
// mirrors pipe()'s own short-circuit test. Requires SOURCE to be
181
// store-free so the guard can evaluate it more than once.
182
class PIPE_FUSION_RECOGNIZER(_innate_symbol_lookup: Semantic.Lookups.InnateSymbolLookup) is
183
recognize(`for: Trees.Statements.FOR) -> PIPE_FUSION? =>
184
recognize_any(`for.expression);
185
186
// Peel either chain shape off `expression`: a `Pipe[T]` method
187
// chain (`pipe(xs).map(f)`) or a chain of `Ghul.Pipes` free
188
// functions (`xs |> map(f)`, desugared at parse time into ordinary
189
// calls - see recognize_free_function_chain). Used both by the
190
// `for`-loop path and by consumer fusion, since a terminal
191
// consumer's receiver can be written in either form.
192
recognize_any(expression: Trees.Expressions.Expression?) -> PIPE_FUSION? is
193
let chain = recognize_chain(expression);
194
195
if chain? then
196
return chain;
197
fi
198
199
return recognize_free_function_chain(expression);
200
si
201
202
// Peel a `... |> map(f) |> filter(p)` chain of `Ghul.Pipes` free
203
// functions off an arbitrary expression. `|>` is desugared entirely
204
// at parse time into an ordinary CALL with the threaded value
205
// inserted as argument 0, so by the time this pass runs `xs |>
206
// map(f)` is indistinguishable from `map(xs, f)` - a plain
207
// global-function call resolved once via ordinary overload
208
// resolution.
209
//
210
// Soundness: `Ghul.Pipes.map`/`filter`/`take`/`skip` are global
211
// functions with no receiver, so a call to one is never a member
212
// access and never reaches an overridden `Pipe[T].map`/`filter` -
213
// fused or not. There is no isa-based dispatch anywhere in the call
214
// for a guard to route around, so `needs_guard` is always false
215
// regardless of the source's static or dynamic type.
216
recognize_free_function_chain(expression: Trees.Expressions.Expression?) -> PIPE_FUSION? is
217
if !expression? then
218
return null;
219
fi
220
221
let stages = LIST[PIPE_FUSION_STAGE]();
222
223
let current mut = expression;
224
225
while isa Trees.Expressions.CALL(current) do
226
let call = cast Trees.Expressions.CALL(current);
227
228
let stage = _classify_free_function_stage(call);
229
230
if !stage? then
231
break;
232
fi
233
234
stages.add(stage);
235
236
current = call.arguments.expressions[0];
237
od
238
239
if stages.count == 0 then
240
return null;
241
fi
242
243
let source = current;
244
let source_value = source.value;
245
246
if !source_value? \/ !source_value.type? then
247
return null;
248
fi
249
250
return PIPE_FUSION(source, stages, false);
251
si
252
253
// Classify `call` as a fusible `Ghul.Pipes` free-function stage -
254
// map, filter, take or skip - matching the same stage shapes the
255
// method-chain recognizer above builds, checked against the
256
// compiled IR rather than the AST since a global-function call
257
// carries no receiver to inspect syntactically. Returns null for
258
// any other `Ghul.Pipes` function or any non-Pipes call, which
259
// stops the peel loop and leaves the call as an ordinary, unfused
260
// expression - still correct, since an unrecognised stage drives
261
// its own result through its own iterator exactly as the unfused
262
// lowering would.
263
_classify_free_function_stage(call: Trees.Expressions.CALL) -> PIPE_FUSION_STAGE? is
264
let value = call.value;
265
266
if !isa IR.Values.Call.GLOBAL(value) then
267
return null;
268
fi
269
270
let global_call = cast IR.Values.Call.GLOBAL(value);
271
let qualified_name = global_call.function.qualified_name;
272
273
if call.arguments.expressions.count != 2 then
274
return null;
275
fi
276
277
if qualified_name =~ "Ghul.Pipes.map" \/ qualified_name =~ "Ghul.Pipes.filter" then
278
return PIPE_FUSION_STAGE(qualified_name =~ "Ghul.Pipes.filter", call.arguments.expressions[1]);
279
fi
280
281
if qualified_name =~ "Ghul.Pipes.take" \/ qualified_name =~ "Ghul.Pipes.skip" then
282
return PIPE_FUSION_STAGE(qualified_name =~ "Ghul.Pipes.take", qualified_name =~ "Ghul.Pipes.skip", call.arguments.expressions[1]);
283
fi
284
285
return null;
286
si
287
288
// Peel a `pipe(SOURCE).map(f).filter(p).index()...` chain off an
289
// arbitrary expression - the iterated expression of a `for` loop, or
290
// the receiver of a terminal consumer (`.collect()`, `.find(p)`, ...).
291
recognize_chain(expression: Trees.Expressions.Expression?) -> PIPE_FUSION? is
292
let pipe_type = _innate_symbol_lookup.get_unspecialized_pipe_type();
293
294
if !pipe_type? then
295
return null;
296
fi
297
298
if !expression? then
299
return null;
300
fi
301
302
let stages = LIST[PIPE_FUSION_STAGE]();
303
304
let current mut = expression;
305
306
// Peel `map`/`filter` layers off the outside of the chain.
307
while isa Trees.Expressions.CALL(current) do
308
let call = cast Trees.Expressions.CALL(current);
309
310
if !isa Trees.Expressions.MEMBER(call.function) then
311
break;
312
fi
313
314
let member = cast Trees.Expressions.MEMBER(call.function);
315
let name = member.identifier.name;
316
317
let is_filter = name =~ "filter";
318
let is_map = name =~ "map";
319
let is_index = name =~ "index";
320
let is_take = name =~ "take";
321
let is_skip = name =~ "skip";
322
323
if !(is_filter \/ is_map \/ is_index \/ is_take \/ is_skip) then
324
break;
325
fi
326
327
// The receiver must be statically a Pipe[T]. On a trait
328
// static type overload resolution binds the default op, so
329
// this identifies the default map/filter/index/take/skip.
330
if !_is_pipe_expression(member.left, pipe_type) then
331
break;
332
fi
333
334
if is_take \/ is_skip then
335
if call.arguments.expressions.count != 1 then
336
break;
337
fi
338
339
stages.add(PIPE_FUSION_STAGE(is_take, is_skip, call.arguments.expressions[0]));
340
elif is_index then
341
// Only the no-argument `index()` (start 0) is fused;
342
// `index(start)` is left to the class-based pipe.
343
if call.arguments.expressions.count != 0 then
344
break;
345
fi
346
347
let stage = PIPE_FUSION_STAGE(0);
348
349
// The call's type is Pipe[INDEXED_VALUE[element]];
350
// extract INDEXED_VALUE[element] for the loop to build.
351
let call_value = call.value;
352
353
if !call_value? \/ !call_value.type? then
354
break;
355
fi
356
357
stage.indexed_value_type = Semantic.Symbols.TYPE_ARGUMENT_EXTRACTOR.extract(call_value.type!, pipe_type);
358
359
if !stage.indexed_value_type? then
360
break;
361
fi
362
363
stages.add(stage);
364
else
365
if call.arguments.expressions.count != 1 then
366
break;
367
fi
368
369
stages.add(PIPE_FUSION_STAGE(is_filter, call.arguments.expressions[0]));
370
fi
371
372
current = member.left;
373
od
374
375
// A chain with no map/filter/take/skip/index stages still fuses:
376
// a bare `pipe(SOURCE)` fed to a `for` loop or a terminal
377
// consumer iterates SOURCE directly, so the wrapping ADAPTOR_PIPE
378
// (and, for a sealed value-type source, the box) is never built.
379
// The `is_pipe_wrap` base check below remains the real gate - a
380
// non-pipe expression never reaches here.
381
382
// The base must be a `pipe(SOURCE)` wrap.
383
if !isa Trees.Expressions.CALL(current) then
384
return null;
385
fi
386
387
let base_call = cast Trees.Expressions.CALL(current);
388
389
if !base_call.is_pipe_wrap then
390
return null;
391
fi
392
393
if base_call.arguments.expressions.count != 1 then
394
return null;
395
fi
396
397
let source = base_call.arguments.expressions[0];
398
let source_value = source.value;
399
400
if !source_value? \/ !source_value.type? then
401
return null;
402
fi
403
404
let source_type = source_value.type!;
405
406
let classification = classify_source_type(source_type, pipe_type);
407
408
if !classification? then
409
return null;
410
fi
411
412
let needs_guard = classification;
413
414
// The guarded loop re-emits SOURCE's value (once for the `isa`
415
// test, again for iteration), so its IR must be safe to emit
416
// more than once: store-free (no repeated side effect) and not
417
// a BLOCK (the one single-shot IR value - `is_emitted` aborts a
418
// second gen). Real sources are plain field/local loads, which
419
// satisfy both.
420
if needs_guard /\ (source_value.is_state_changing_call \/ isa IR.Values.BLOCK(source_value)) then
421
return null;
422
fi
423
424
// A guarded loop also emits each take/skip count twice - once
425
// into the fused counter, once in the fallback pipe chain - so a
426
// count fed to a guarded fusion has the same emit-more-than-once
427
// requirement as the source. Counts are almost always literals,
428
// which satisfy it.
429
if needs_guard then
430
for stage in stages do
431
if stage.is_countdown then
432
let count_value = stage.argument!.value;
433
434
if !count_value? \/ count_value.is_state_changing_call \/ isa IR.Values.BLOCK(count_value) then
435
return null;
436
fi
437
fi
438
od
439
fi
440
441
return PIPE_FUSION(source, stages, needs_guard);
442
si
443
444
// Classify a fusion base by its static source type:
445
//
446
// - null: do not fuse. The source is statically a Pipe, so `pipe()`
447
// short-circuits to it and runs its (possibly overridden)
448
// map/filter - a runtime guard would always take the fallback, so
449
// there is nothing to gain.
450
// - false: fuse unconditionally. A sealed source (value type or
451
// array) has a dynamic type equal to its static type, so it cannot
452
// secretly be a user Pipe with an override.
453
// - true: fuse behind the runtime `isa Pipe[element]` guard. Any
454
// other source is only *statically* not a Pipe; its dynamic type
455
// could be a user Pipe, and the guard mirrors `pipe()`'s own
456
// short-circuit test.
457
classify_source_type(source_type: Types.Type, pipe_type: Types.Type) -> bool? is
458
if _is_pipe_type(source_type, pipe_type) then
459
return null;
460
fi
461
462
if source_type.is_value_type \/ isa Semantic.Types.ARRAY(source_type) then
463
return false;
464
fi
465
466
return true;
467
si
468
469
_is_pipe_expression(expression: Trees.Expressions.Expression, pipe_type: Types.Type) -> bool is
470
let value = expression.value;
471
472
if !value? \/ !value.type? then
473
return false;
474
fi
475
476
return _is_pipe_type(value.type!, pipe_type);
477
si
478
479
_is_pipe_type(type: Types.Type, pipe_type: Types.Type) -> bool =>
480
Semantic.Symbols.TYPE_ARGUMENT_EXTRACTOR.extract(type, pipe_type)?;
481
si
482
si