Skip to content
← Back

src/ir/emitter/structured_lowering.ghul

1
@@IF.dotnet()
2
3
namespace IR.Emitter is
4
use System.Reflection.Metadata.ILOpCode
5
6
use Ghul.Pipes
7
8
use IR.BRANCH
9
use IR.Values.Breakable
10
use IR.Values.BLOCK
11
use IR.Values.DISPATCH
12
use IR.Values.Exit
13
use IR.Values.CONTINUE
14
use IR.Values.LOOP
15
use IR.Values.REGION
16
use IR.Values.RESUMABLE
17
use IR.Values.RESUME_POINT
18
use IR.Values.TRY
19
use IR.Values.Value
20
21
// Lowers structured control flow to the flat form the CIL emitter
22
// consumes: labels, branches and the values between them, in the
23
// order they are encoded.
24
//
25
// Lowering is one level deep. A structured node in another's body
26
// stays a value in the flat sequence and lowers itself when it is
27
// generated, so the nodes open at any point are exactly those
28
// being generated.
29
class STRUCTURED_LOWERING is
30
linearise(value: Value) -> Collections.List[Value] static =>
31
linearise(value, Collections.LIST[Breakable]())
32
33
// Lowers `value` as if generated inside `open`, innermost first.
34
linearise(value: Value, open: Collections.Iterable[Breakable]) -> Collections.List[Value] static =>
35
_linearise(value, open) |> map(f => f.value) |> collect()
36
37
// An exit leaves a protected region where its target is a try,
38
// or a try is open inside its target.
39
leaves_protected_region(target: Breakable, open: Collections.Iterable[Breakable]) -> bool static is
40
for node in open do
41
if isa TRY(node) then
42
return true
43
elif node == target then
44
return false
45
fi
46
od
47
48
return false
49
si
50
51
// Encode a structured node by encoding its flat form. A value
52
// from the node's body marks its own position, as it would in a
53
// block; a label or branch the lowering adds marks the position
54
// of the node it was added for.
55
gen(value: Value, context: IR.Emitter.CIL_CONTEXT) static is
56
let breakable = if isa Breakable(value) then cast Breakable(value) else null fi
57
58
if breakable? then
59
context.enter_structured(breakable)
60
elif isa Exit(value) then
61
let exit = cast Exit(value)
62
63
assert context.is_structured_open(exit.target) else "exit outside the node it leaves: {exit}"
64
fi
65
66
for flat in _linearise(value, context.open_structured) do
67
if flat.position? /\ context.is_marking_structure then
68
context.mark_location(flat.position)
69
fi
70
71
context.lowering.gen(flat.value)
72
od
73
74
if breakable? then
75
context.leave_structured(breakable)
76
fi
77
si
78
79
branch_instruction(condition: BRANCH) -> ILOpCode static =>
80
case condition
81
when BRANCH.EQ then ILOpCode.BEQ
82
when BRANCH.GE then ILOpCode.BGE
83
when BRANCH.GEU then ILOpCode.BGE_UN
84
when BRANCH.GT then ILOpCode.BGT
85
when BRANCH.GTU then ILOpCode.BGT_UN
86
when BRANCH.LE then ILOpCode.BLE
87
when BRANCH.LEU then ILOpCode.BLE_UN
88
when BRANCH.LT then ILOpCode.BLT
89
when BRANCH.LTU then ILOpCode.BLT_UN
90
when BRANCH.NE then ILOpCode.BNE_UN
91
when BRANCH.Z then ILOpCode.BRFALSE
92
when BRANCH.NZ then ILOpCode.BRTRUE
93
when BRANCH.ALWAYS then ILOpCode.BR
94
else throw System.InvalidOperationException("no branch instruction for {condition}")
95
esac
96
97
_linearise(value: Value, open: Collections.Iterable[Breakable]) -> Collections.List[FLAT_VALUE] static is
98
let result = Collections.LIST[FLAT_VALUE]()
99
100
if isa LOOP(value) then
101
_linearise_loop(cast LOOP(value), result)
102
elif isa TRY(value) then
103
_linearise_try(cast TRY(value), result)
104
elif isa RESUMABLE(value) then
105
_linearise_resumable(cast RESUMABLE(value), result)
106
elif isa DISPATCH(value) then
107
_linearise_dispatch(cast DISPATCH(value), result)
108
elif isa RESUME_POINT(value) then
109
let resume = cast RESUME_POINT(value)
110
111
result.add(FLAT_VALUE(MARK_LABEL(resume.label), resume.position))
112
elif isa REGION(value) then
113
_linearise_region(cast REGION(value), result)
114
elif isa Exit(value) then
115
_linearise_exit(cast Exit(value), open, result)
116
else
117
result.add(FLAT_VALUE.of(value))
118
fi
119
120
return result
121
si
122
123
_linearise_loop(loop: LOOP, into: Collections.MutableList[FLAT_VALUE]) static is
124
into.add(FLAT_VALUE(MARK_LABEL(loop.start), loop.position))
125
126
_linearise_body(loop, into)
127
128
into.add(FLAT_VALUE(BRANCH_TO(ILOpCode.BR, loop.start), loop.position))
129
into.add(FLAT_VALUE(MARK_LABEL(loop.end), loop.position))
130
si
131
132
_linearise_region(region: REGION, into: Collections.MutableList[FLAT_VALUE]) static is
133
_linearise_body(region, into)
134
135
into.add(FLAT_VALUE(MARK_LABEL(region.end), region.position))
136
si
137
138
_linearise_try(`try: TRY, into: Collections.MutableList[FLAT_VALUE]) static is
139
let extent = TRY_EXTENT()
140
141
into.add(FLAT_VALUE(TRY_START(extent), `try.position))
142
143
_linearise_body(`try, into)
144
145
into.add(FLAT_VALUE(TRY_END(extent), `try.position))
146
147
for `catch in `try.catches do
148
let region = PROTECTED_REGION(extent, `catch.type)
149
150
into.add(FLAT_VALUE(HANDLER_START(region), `catch.position))
151
152
for value in `catch.body.values do
153
into.add(FLAT_VALUE.of(value))
154
od
155
156
into.add(FLAT_VALUE(HANDLER_END(region), `catch.position))
157
od
158
159
if let `finally = `try.finally_region then
160
let region = PROTECTED_REGION(extent, null)
161
162
into.add(FLAT_VALUE(HANDLER_START(region), `finally.position))
163
into.add(FLAT_VALUE(`finally, null))
164
into.add(FLAT_VALUE(INSTRUCTION(ILOpCode.ENDFINALLY), `finally.position))
165
into.add(FLAT_VALUE(HANDLER_END(region), `finally.position))
166
fi
167
168
if `try.is_targeted then
169
into.add(FLAT_VALUE(MARK_LABEL(`try.end), `try.position))
170
fi
171
si
172
173
_linearise_resumable(resumable: RESUMABLE, into: Collections.MutableList[FLAT_VALUE]) static is
174
_linearise_body(resumable, into)
175
176
if resumable.is_targeted then
177
into.add(FLAT_VALUE(MARK_LABEL(resumable.end), resumable.position))
178
fi
179
si
180
181
_linearise_dispatch(dispatch: DISPATCH, into: Collections.MutableList[FLAT_VALUE]) static is
182
into.add(FLAT_VALUE(MARK_LABEL(dispatch.top), dispatch.position))
183
184
let position = dispatch.position
185
186
for entry in dispatch.entries do
187
into.add(FLAT_VALUE.of(IR.Values.Load.TEMP(dispatch.state_local)))
188
into.add(FLAT_VALUE(IR.Values.Literal.NUMBER(entry.state, dispatch.state_type), position))
189
into.add(FLAT_VALUE(BRANCH_TO(ILOpCode.BEQ, entry.target), position))
190
od
191
si
192
193
_linearise_body(node: Breakable, into: Collections.MutableList[FLAT_VALUE]) static is
194
for value in node.body.values do
195
into.add(FLAT_VALUE.of(value))
196
od
197
si
198
199
_linearise_exit(exit: Exit, open: Collections.Iterable[Breakable], into: Collections.MutableList[FLAT_VALUE]) static is
200
let target =
201
if let `continue: CONTINUE = exit then
202
`continue.loop.start
203
else
204
exit.target.end
205
fi
206
207
let leaves_protected_region = leaves_protected_region(exit.target, open)
208
209
if exit.condition == BRANCH.ALWAYS then
210
let op_code =
211
if leaves_protected_region then
212
ILOpCode.LEAVE
213
else
214
ILOpCode.BR
215
fi
216
217
into.add(FLAT_VALUE(BRANCH_TO(op_code, target), exit.position))
218
219
return
220
fi
221
222
assert !leaves_protected_region else "conditional exit from a protected region: {exit}"
223
224
for operand in exit.operands do
225
into.add(FLAT_VALUE.of(operand))
226
od
227
228
into.add(FLAT_VALUE(BRANCH_TO(branch_instruction(exit.condition), target), exit.position))
229
si
230
si
231
232
// A value in a lowered sequence, with the source position to mark
233
// before it is encoded.
234
class FLAT_VALUE(value: Values.Value, position: Source.LOCATION?) is
235
of(value: Values.Value) -> FLAT_VALUE static =>
236
FLAT_VALUE(
237
value,
238
if value.has_location then value.location else null fi)
239
si
240
si