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): `argument` is the start, or null to start
11
// at zero; the loop keeps a running counter 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
// A fourth kind is transparent: a `memo` stage (is_noop true) is
17
// recognised but never added to a chain's stage list. A memo pipe
18
// consumed inline by the one `for` loop or terminal consumer that
19
// fuses a chain is unobservable - its cache is never read a second
20
// time and its source runs exactly once with or without it - so the
21
// chain fuses as though the memo were absent. The MEMO_PIPE itself is
22
// then never constructed; wherever the chain does not fuse, the memo
23
// is built and behaves exactly as written.
24
//
25
// For a map/filter stage whose `argument` is an inlinable literal
26
// lambda, compile-expressions fills `param_local` (a synthetic
27
// enclosing-method local the loop assigns the incoming element to) and
28
// `inline_body` (the lambda body re-walked in the enclosing scope, so
29
// its parameter loads that local and its captures load ordinary
30
// enclosing locals - no delegate, no closure frame). When both are set
31
// the loop emits the body inline; otherwise it invokes the argument's
32
// compiled delegate value.
33
class PIPE_FUSION_STAGE is
34
is_filter: bool public
35
is_index: bool public
36
is_noop: bool public
37
38
// A `take`/`skip` stage: `argument` is the int count expression,
39
// evaluated once into a running counter that the loop decrements per
40
// pulled element (take stops the loop when it runs out; skip drops
41
// the element while it remains).
42
is_take: bool public
43
is_skip: bool public
44
45
// The stage's argument: a map/filter lambda or delegate, the int
46
// count of a take/skip stage, or an index stage's start. Null for
47
// an index stage that starts at zero.
48
argument: Trees.Expressions.Expression? public
49
50
// Index stage only. `chain_type` is the `index` call's own type,
51
// `Pipe[INDEXED_VALUE[E]]`, from which compile-expressions reads
52
// the INDEXED_VALUE the loop builds per element and resolves its
53
// constructor. `argument`, when present, is the start the caller
54
// supplied, evaluated once into the running counter exactly as a
55
// take/skip count is; absent, the counter starts at zero.
56
chain_type: Semantic.Types.Type? public
57
indexed_value_type: Semantic.Types.Type? public
58
indexed_value_constructor: Semantic.Symbols.Function? public
59
60
param_local: Semantic.Symbols.Variable? public
61
62
inline_body: IR.Values.Value? public
63
64
// The literal whose body this stage inlines, so the emission site
65
// can have its body walked into the block it emits.
66
inlined_closure: Semantic.Symbols.Closure? public
67
68
// A take/skip stage keeps a running counter but transforms nothing,
69
// so the element passes through unchanged.
70
is_countdown: bool => is_take \/ is_skip
71
72
is_inlined: bool => param_local? /\ inline_body?
73
74
// A fusible index stage needs both its type and constructor
75
// resolved; otherwise the recogniser rejects the chain.
76
is_index_ready: bool => indexed_value_type? /\ indexed_value_constructor?
77
78
init(is_filter: bool, argument: Trees.Expressions.Expression) is
79
self.is_filter = is_filter
80
self.argument = argument
81
si
82
83
init(chain_type: Semantic.Types.Type, start: Trees.Expressions.Expression?) is
84
self.is_index = true
85
self.chain_type = chain_type
86
self.argument = start
87
si
88
89
init(is_take: bool, is_skip: bool, count: Trees.Expressions.Expression) is
90
self.is_take = is_take
91
self.is_skip = is_skip
92
self.argument = count
93
si
94
95
init() is
96
is_noop = true
97
si
98
si
99
100
// The literals written inside a stage body, outermost first. Each
101
// one's captures are recorded against the symbols its enclosing
102
// literal owned, so they are dropped before the body is walked
103
// inline and recorded afresh against the method's own locals.
104
class NESTED_LITERAL_COLLECTOR: Visitor is
105
_literals: LIST[Trees.Expressions.FUNCTION]
106
107
init() is
108
super.init()
109
110
_literals = LIST[Trees.Expressions.FUNCTION]()
111
si
112
113
collect(body: Trees.Bodies.Body?) -> Collections.List[Trees.Expressions.FUNCTION] is
114
_literals.clear()
115
116
if body? then
117
body.walk(self)
118
fi
119
120
return _literals
121
si
122
123
pre(function: Trees.Expressions.FUNCTION) -> bool is
124
_literals.add(function)
125
126
return false
127
si
128
si
129
130
// A recognised fusible pipe chain rooted at a `for` loop. `source` is
131
// the iterable the chain starts from; the fused loop iterates it
132
// directly - so no pipe object is built for it - and applies `stages`
133
// inline per element. `stages`
134
// are outermost-first (the order they wrap the source), so inline
135
// application walks them in reverse.
136
class PIPE_FUSION(source: Trees.Expressions.Expression, stages_outermost_first: LIST[PIPE_FUSION_STAGE]) is
137
source: Trees.Expressions.Expression public
138
stages_outermost_first: LIST[PIPE_FUSION_STAGE] public
139
140
// The source's own iterator members, resolved against its type
141
// exactly as a plain `for x in source` would. read_iterator is
142
// null when the source is directly an iterator (e.g. a range);
143
// otherwise it yields the iterator that move_next / read_current
144
// drive. Filled by compile-expressions after recognition.
145
source_read_iterator: Semantic.Symbols.Function? public
146
source_move_next: Semantic.Symbols.Function? public
147
source_read_current: Semantic.Symbols.Function? public
148
si
149
150
// Decides whether a `for x in <chain>` loop's expression is a
151
// fusible pipe chain, and if so returns the plan the IL pass
152
// consumes. Pure recognition — no compilation side effects.
153
//
154
// A chain is a run of `Ghul.Pipes` free-function calls, which have no
155
// receiver, so no call in one can reach a `Pipe[T]` implementation
156
// that overrides a combinator: what a stage does is settled by the
157
// function the call resolved to. Nothing about the source's dynamic
158
// type can change that, so a chain fuses whatever it starts from -
159
// see `recognize_free_function_chain`.
160
class PIPE_FUSION_RECOGNIZER(fusion_functions: Collections.MAP[Semantic.Symbols.Symbol, string]) is
161
162
// Why the last recognition declined, and the roles of whatever
163
// chain it had peeled when it did, outermost first. Read by the
164
// pipe-fusion study; nothing the compiler decides depends on
165
// either. A recogniser is constructed per recognition, so they
166
// describe that one.
167
decline_reason: string?
168
peeled_roles: string?
169
170
// The role the last successful classification named.
171
_last_role: string?
172
173
// The function the peel loop stopped at, when it stopped at a
174
// global call fusion has no stage for. Read by the pipe-fusion
175
// study, which asks whether it is a Ghul.Pipes combinator and so
176
// a stage worth teaching the fuser.
177
boundary_function: Semantic.Symbols.Function?
178
179
// A `for` needs a stage to fuse. Its expression is whatever the
180
// loop iterates, so accepting a chain of no stages here would take
181
// every `for` in every program through the fused loop rather than
182
// the ordinary one - a change to how all iteration is emitted,
183
// which is not this path's to make.
184
recognize(`for: Trees.Statements.FOR) -> PIPE_FUSION? =>
185
recognize_free_function_chain(`for.expression, false)
186
187
// Peel a chain of `Ghul.Pipes` free functions off `expression`, for
188
// a consumer, which fuses over a chain of no stages as well: a bare
189
// `xs |> sum()` has nothing between the consumer and its source.
190
recognize_any(expression: Trees.Expressions.Expression?) -> PIPE_FUSION? =>
191
recognize_free_function_chain(expression, true)
192
193
// Peel a `... |> map(f) |> filter(p)` chain of `Ghul.Pipes` free
194
// functions off an arbitrary expression. `|>` is desugared entirely
195
// at parse time into an ordinary CALL with the threaded value
196
// inserted as argument 0, so by the time this pass runs `xs |>
197
// map(f)` is indistinguishable from `map(xs, f)` - a plain
198
// global-function call resolved once via ordinary overload
199
// resolution.
200
//
201
// Soundness, dispatch: `Ghul.Pipes.map`/`filter`/`take`/`skip` are
202
// global functions with no receiver, so a call to one is never a
203
// member access and never reaches an overridden `Pipe[T].map`/
204
// `filter` - fused or not, whatever the source's static or
205
// dynamic type.
206
//
207
// A source that is itself a Pipe also fuses, because a
208
// thread-first chain is routinely written straight off a
209
// generator or a `stream`. The loop reads it through a fresh
210
// iterator, as a plain `for` does.
211
recognize_free_function_chain(expression: Trees.Expressions.Expression?) -> PIPE_FUSION? =>
212
recognize_free_function_chain(expression, true)
213
214
recognize_free_function_chain(expression: Trees.Expressions.Expression?, allow_no_stages: bool) -> PIPE_FUSION? is
215
if !expression? then
216
decline_reason = "no-expression"
217
218
return null
219
fi
220
221
let stages = LIST[PIPE_FUSION_STAGE]()
222
let roles = LIST[string]()
223
224
let current mut = expression
225
let calls mut = 0
226
227
while isa Trees.Expressions.CALL(current) do
228
let call = cast Trees.Expressions.CALL(current)
229
230
let stage = _classify_free_function_stage(call)
231
232
if !stage? then
233
break
234
fi
235
236
calls = calls + 1
237
roles.add(_last_role ?? "?")
238
239
// A memo stage is elided rather than fused: the chain
240
// fuses as though it were absent (see PIPE_FUSION_STAGE).
241
if !stage.is_noop then
242
stages.add(stage)
243
fi
244
245
current = call.arguments.expressions[0]
246
od
247
248
// An expression that peeled no stage is still a chain of no
249
// stages, which a consumer fuses over directly: the loop reads
250
// the source and applies the consumer, as the stage-free path
251
// already did for a chain whose only stage was a memo. Whatever
252
// the source turns out to be - a local, a call, a generator -
253
// the loop reads it through one fresh iterator, exactly as the
254
// unfused consumer would. A `for` declines it instead, keeping
255
// ordinary iteration on the lowering it has always had.
256
if !allow_no_stages /\ calls == 0 then
257
decline_reason = "not-a-chain"
258
259
return null
260
fi
261
262
let joined = System.Text.StringBuilder()
263
264
for role in roles do
265
if joined.length > 0 then
266
joined.append(",")
267
fi
268
269
joined.append(role)
270
od
271
272
peeled_roles = joined.to_string()
273
274
let source = current
275
let source_value = source.value
276
277
if !source_value? \/ !source_value.type? then
278
decline_reason = "source-not-compiled"
279
280
return null
281
fi
282
283
return PIPE_FUSION(source, stages)
284
si
285
286
// Classify `call` as a fusible `Ghul.Pipes` free-function stage -
287
// map, filter, take, skip or index, or a `memo` stage that is
288
// recognised only to be elided - by comparing the resolved call
289
// target against the fusible-combinator symbols, so what fuses
290
// follows the function the call bound rather than how it spells
291
// itself. Returns null for any other function, which stops the
292
// peel loop and leaves the call as an ordinary, unfused
293
// expression - still correct, since an unrecognised stage drives
294
// its own result through its own iterator exactly as the unfused
295
// lowering would.
296
_classify_free_function_stage(call: Trees.Expressions.CALL) -> PIPE_FUSION_STAGE? is
297
let value = call.value
298
299
if !isa IR.Values.Call.GLOBAL(value) then
300
return null
301
fi
302
303
let global_call = cast IR.Values.Call.GLOBAL(value)
304
let role: string mut
305
306
if !fusion_functions.try_get_value(global_call.function.root_specialized_from, role ref) then
307
boundary_function = global_call.function
308
309
return null
310
fi
311
312
_last_role = role
313
boundary_function = null
314
315
let arguments = call.arguments.expressions
316
317
if role =~ "memo" then
318
if arguments.count != 1 then
319
return null
320
fi
321
322
return PIPE_FUSION_STAGE()
323
fi
324
325
// `index` comes in both arities: from zero, or from a start
326
// the caller supplies. The stage carries the call's own type,
327
// which is where the INDEXED_VALUE it builds per element is
328
// read from rather than reconstructed.
329
if role =~ "index" then
330
let chain_type = value.type
331
332
if arguments.count == 1 then
333
return PIPE_FUSION_STAGE(chain_type, null)
334
elif arguments.count == 2 then
335
return PIPE_FUSION_STAGE(chain_type, arguments[1])
336
fi
337
338
339
return null
340
fi
341
342
if arguments.count != 2 then
343
return null
344
fi
345
346
if role =~ "map" \/ role =~ "filter" then
347
return PIPE_FUSION_STAGE(role =~ "filter", arguments[1])
348
fi
349
350
if role =~ "take" \/ role =~ "skip" then
351
return PIPE_FUSION_STAGE(role =~ "take", role =~ "skip", arguments[1])
352
fi
353
354
// A consumer role - the peel loop's source boundary, which is
355
// where a chain ends rather than where one fails.
356
357
return null
358
si
359
si
360
si