1 /* pkl-pass.h - Support for compiler passes. */
2
3 /* Copyright (C) 2019, 2020, 2021 Jose E. Marchesi */
4
5 /* This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #ifndef PKL_PASS_H
20 #define PKL_PASS_H
21
22 #include <config.h>
23
24 #include <assert.h>
25 #include <setjmp.h>
26 #include <inttypes.h>
27 #include <stdarg.h>
28
29 #include "pkl.h"
30 #include "pkl-diag.h"
31 #include "pkl-ast.h"
32
33 /* A `pass' is a complete run over a given AST. A `phase' is an
34 analysis or a transformation performed over a subset of the nodes
35 in the AST. One pass may integrate several phases.
36
37 Implementing a phase involves defining a struct pkl_phase variable
38 and filling it up. A pkl_phase struct contains:
39
40 - CODE_PS_HANDLERS is a table indexed by node codes, which must be
41 values in the `pkl_ast_code' enumeration defined in pkl-ast.h.
42 For example, PKL_AST_ARRAY. It maps codes to
43 pkl_phase_handler_fn functions.
44
45 - OP_PS_HANDLERS is a table indexed by operator codes, which must
46 be values in the `pkl_ast_op' enumeration defined in pkl-ast.h.
47 This enumeration is in turn generated from the operators defined
48 in pkl-ops.def. For example, PKL_AST_OP_ADD. It maps codes to
49 pkl_phase_handler_fn functions.
50
51 - TYPE_PS_HANDLERS is a table indexed by type codes, which must be
52 values in the `pkl_ast_type_code' enumeration defined in
53 pkl-ast.h. For example, PKL_TYPE_STRING. It maps codes to
54 pkl_phase_handler_fn functions.
55
56 The handlers defined in the tables above are invoked while
57 traversing the AST in a post-order depth-first fashion. Additional
58 tables exist to define handlers that are executed while traversing
59 the AST a pre-order depth-first fashion:
60
61 - CODE_PR_HANDLERS
62 - OP_PR_HANDLERS
63 - TYPE_PR_HANDLERS
64
65 A given phase can define handlers of both types: PR (pre-order) and
66 PS (post-order).
67
68 There are three additional handlers that the user can install:
69
70 - DEFAULT_PR_HANDLER is invoked for every node in the AST, after the
71 more particular ones, in pre-order.
72
73 - DEFAULT_PS_HANDLER is invoked for every node in the AST, after
74 the more particular ones, in post-order.
75
76 - ELSE_HANDLER, if not NULL, is invoked for every node for which no
77 other handler (PR or PS) has been invoked.
78
79 Note that if a given node class falls in several categories as
80 implemented in the handlers tables, the order in which the
81 different kind of handlers are executed depend on the ordering:
82
83 - Pre-order handlers are executed from more generic to more
84 particular. For example, for a PKL_AST_TYPE node with type code
85 PKL_TYPE_ARRAY, the handler in `code_pr_handlers' will be invoked
86 first, followed by the handler in `type_pr_handlers'.
87
88 - Post-order handlers are executed from more particular to more
89 generic. For example, for a PKL_AST_TYPE node with the type code
90 PKL_TYPE_ARRAY, the handler in `type_ps_handlers' will be invoked
91 first, followed by the handler in `code_ps_handlers'.
92
93 If the `else' handler is NULL and no other handler is executed,
94 then no action is performed on a node other than traversing it. */
95
96 struct pkl_phase; /* Forward declaration. */
97
98 typedef pkl_ast_node (*pkl_phase_handler_fn) (pkl_compiler compiler,
99 jmp_buf toplevel,
100 pkl_ast ast,
101 pkl_ast_node node,
102 void *payload,
103 int *restart,
104 size_t child_pos,
105 pkl_ast_node parent,
106 int *dobreak,
107 void *payloads[],
108 struct pkl_phase *phases[],
109 int flags,
110 int level);
111
112 struct pkl_phase
113 {
114 pkl_phase_handler_fn else_handler;
115
116 pkl_phase_handler_fn default_ps_handler;
117 pkl_phase_handler_fn code_ps_handlers[PKL_AST_LAST];
118 pkl_phase_handler_fn op_ps_handlers[PKL_AST_OP_LAST];
119 pkl_phase_handler_fn type_ps_handlers[PKL_TYPE_NOTYPE];
120
121 pkl_phase_handler_fn default_pr_handler;
122 pkl_phase_handler_fn code_pr_handlers[PKL_AST_LAST];
123 pkl_phase_handler_fn op_pr_handlers[PKL_AST_OP_LAST];
124 pkl_phase_handler_fn type_pr_handlers[PKL_TYPE_NOTYPE];
125 };
126
127 typedef struct pkl_phase *pkl_phase;
128
129 /* The following macros should be used in order to register handlers
130 in a `struct pkl_phase'. This allows changing the structure layout
131 without impacting the phase definitions. */
132
133 #define PKL_PHASE_ELSE_HANDLER(handler) \
134 .else_handler = handler
135
136 #define PKL_PHASE_PR_DEFAULT_HANDLER(handler) \
137 .default_pr_handler = handler
138 #define PKL_PHASE_PS_DEFAULT_HANDLER(handler) \
139 .default_ps_handler = handler
140
141 #define PKL_PHASE_PR_HANDLER(code, handler) \
142 .code_pr_handlers[code] = handler
143 #define PKL_PHASE_PS_HANDLER(code, handler) \
144 .code_ps_handlers[code] = handler
145
146 #define PKL_PHASE_PR_OP_HANDLER(code,handler) \
147 .op_pr_handlers[code] = handler
148 #define PKL_PHASE_PS_OP_HANDLER(code,handler) \
149 .op_ps_handlers[code] = handler
150
151 #define PKL_PHASE_PR_TYPE_HANDLER(code,handler) \
152 .type_pr_handlers[code] = handler
153 #define PKL_PHASE_PS_TYPE_HANDLER(code,handler) \
154 .type_ps_handlers[code] = handler
155
156 /* The following macros are available to be used in the body of a node
157 handler:
158
159 PKL_PASS_COMPILER expands to an l-value holding the compiler
160 executing the pass.
161
162 PKL_PASS_PAYLOAD expands to an l-value holding the data pointer
163 passed to `pkl_do_pass'.
164
165 PKL_PASS_AST expands to an l-value holding the pkl_ast value
166 corresponding to the AST being processed.
167
168 PKL_PASS_NODE expands to an l-value holding the pkl_ast_node for
169 the node being processed.
170
171 PKL_PASS_PARENT expands to an l-value holding the pkl_ast_node for
172 the parent of the node being processed. This is NULL for the
173 top-level node in the AST.
174
175 PKL_PASS_CHILD_POS expands to an l-value holding the position (zero
176 based) of the node being processed in the parent's node chain. If
177 the node is not part of a chain, this holds 0.
178
179 PKL_PASS_DONE finishes the execution of the node handler. This is
180 equivalent to reaching the end of the handler body.
181
182 PKL_PASS_BREAK causes the pass manager to not process the children
183 of the current node. This should only be used in a PR handler.
184
185 PKL_PASS_RESTART expands to an l-value that should be set to 1 if
186 the handler modifies its subtree structure in any way, either
187 creating new nodes or removing existing nodes. This makes the pass
188 machinery do the right thing (hopefully.) By default its value is
189 0. This macro should _not_ be used as an r-value. Also, setting
190 PKL_PASS_RESTART to 1 should only be done in PS handlers.
191
192 PKL_PASS_SUBPASS (NODE) starts a subpass that processes the subtree
193 starting at NODE. The subpass shares the same payloads than the
194 current pass. If the execution of the subpass returns an error
195 then the expansion of this macro calls PKL_PASS_ERROR.
196
197 PKL_PASS_EXIT can be used in order to interrupt the execution of
198 the compiler pass, making `pkl_do_pass' to return a non-error code.
199
200 PKL_PASS_ERROR can be used in order to interrupt the execution of
201 the compiler pass, making `pkl_do_pass' to return an error code.
202
203 If you use PKL_PASS_EXIT or PKL_PASS_ERROR, please make sure to
204 delete any node you create unless they are linked to the AST.
205 Otherwise you will leak memory. */
206
207 #define PKL_PASS_COMPILER _compiler
208 #define PKL_PASS_PAYLOAD _payload
209 #define PKL_PASS_AST _ast
210 #define PKL_PASS_NODE _node
211 #define PKL_PASS_PARENT _parent
212 #define PKL_PASS_RESTART (*_restart)
213 #define PKL_PASS_CHILD_POS _child_pos
214
215 #define PKL_PASS_SUBPASS(NODE) \
216 do \
217 { \
218 if (!pkl_do_subpass (PKL_PASS_COMPILER, \
219 PKL_PASS_AST, \
220 (NODE), \
221 _phases, \
222 _payloads, \
223 _flags, \
224 _level)) \
225 PKL_PASS_ERROR; \
226 } \
227 while (0)
228
229 #define PKL_PASS_DONE do { goto _exit; } while (0)
230 #define PKL_PASS_BREAK do { *_dobreak = 1; goto _exit; } while (0)
231
232 #define PKL_PASS_EXIT do { longjmp (_toplevel, 1); } while (0)
233 #define PKL_PASS_ERROR do { longjmp (_toplevel, 2); } while (0)
234
235 /* The following macros are used to define phase handlers, like
236 follows:
237
238 PKL_PHASE_BEGIN_HANDLER (handler_name)
239 ... handler prologue ...
240 {
241 ... handler body ...
242 }
243 PKL_PHASE_END_HANDLER
244
245 Only certain macros should be used as the handler prologue. See
246 below. The handler body contains your C code. Reaching the end of
247 the body finishes the execution of the handler. */
248
249 #define PKL_PHASE_BEGIN_HANDLER(name) \
250 static pkl_ast_node name (pkl_compiler _compiler, jmp_buf _toplevel, \
251 pkl_ast _ast, \
252 pkl_ast_node _node, void *_payload, \
253 int *_restart, size_t _child_pos, \
254 pkl_ast_node _parent, int *_dobreak, \
255 void *_payloads[], \
256 struct pkl_phase *_phases[], \
257 int _flags, \
258 int _level) \
259 { \
260 /* printf (#name " on node %" PRIu64 "\n", PKL_AST_UID (_node)); */ \
261 PKL_PASS_RESTART = 0;
262
263 #define PKL_PHASE_END_HANDLER \
264 \
265 goto _exit; /* To avoid compiler warning */ \
266 _exit: \
267 return PKL_PASS_NODE; \
268 }
269
270 /* The PKL_PHASE_PARENT, PKL_PHASE_PARENT_OP and PKL_PHASE_PARENT_TYPE
271 macros can be used in the prologue of a handler in order to delimit
272 its execution to the case where the current node is a child of a
273 node of the given node code/operation code/type code. */
274
275 static inline int
pkl_phase_parent_in(pkl_ast_node parent,int nc,...)276 pkl_phase_parent_in (pkl_ast_node parent,
277 int nc, ...)
278 {
279 va_list valist;
280 int i;
281
282 if (parent == NULL)
283 /* This happens with the top-level node of the AST, or the
284 top-level node of a subpass. */
285 return 1;
286
287 va_start (valist, nc);
288 for (i = 0; i < nc; i++)
289 {
290 int code = va_arg (valist, int);
291 if (PKL_AST_CODE (parent) == code)
292 return 1;
293 }
294 va_end (valist);
295
296 return 0;
297 }
298
299 #define PKL_PHASE_PARENT(NP,...) \
300 if (!pkl_phase_parent_in (PKL_PASS_PARENT, (NP), __VA_ARGS__)) \
301 { \
302 goto _exit; \
303 }
304
305 /* Traverse the given AST, applying the provided phases (or
306 transformations) in sequence to each AST node.
307
308 PHASES is a NULL-terminated array of pointers to node handlers.
309
310 PAYLOADS is an array of pointers to payloads, which will be passed
311 to the node handlers occupying the same position in the PHASES
312 array. There should be as much payloads as phases, and it is not
313 needed to terminate this array with NULL.
314
315 FLAGS is a set of ORed flags, that modify the behavior or
316 pkl_do_pass. Allowed flags are:
317
318 PKL_PASS_F_TYPES
319 Traverse type tags in AST nodes.
320
321 Running several phases in "parallel" in the same pass is good for
322 performance. However, there is an important consideration: if a
323 phase requires to process each AST nodes just once, no restarting
324 phases must precede it in the pass. This is the case of the code
325 generation pass, for example.
326
327 Return 0 if some error occurred during the pass execution. Return
328 1 otherwise. */
329
330 #define PKL_PASS_F_TYPES 1
331
332 int pkl_do_pass (pkl_compiler compiler, pkl_ast ast,
333 struct pkl_phase *phases[], void *payloads[],
334 int flags, int level);
335
336 /* The following function is to be used by the PKL_PASS_SUBPASS macro
337 defined above. */
338
339 int pkl_do_subpass (pkl_compiler compiler, pkl_ast ast, pkl_ast_node node,
340 struct pkl_phase *phases[], void *payloads[],
341 int flags, int level);
342
343 /* Macros to emit a compilation error, a warning or an ICE from a
344 phase handler. Using them reduces verbosity by not passing the
345 compiler and the AST arguments explicitly. */
346
347 #define PKL_ERROR(...) \
348 pkl_error (PKL_PASS_COMPILER, PKL_PASS_AST, __VA_ARGS__)
349
350 #define PKL_WARNING(...) \
351 pkl_warning (PKL_PASS_COMPILER, PKL_PASS_AST, __VA_ARGS__)
352
353 #define PKL_ICE(...) \
354 pkl_ice (PKL_PASS_COMPILER, PKL_PASS_AST, __VA_ARGS__)
355
356 #endif /* PKL_PASS_H */
357