2 * filter-visitor-generate-ir.c
4 * LTTng filter generate intermediate representation
6 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 * This library is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU Lesser General Public License, version 2.1 only,
10 * as published by the Free Software Foundation.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with this library; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29 #include "filter-parser.h"
30 #include "filter-ast.h"
31 #include "filter-ir.h"
34 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
35 struct filter_node
*node
, enum ir_side side
);
38 struct ir_op
*make_op_root(struct ir_op
*child
, enum ir_side side
)
42 op
= calloc(sizeof(struct ir_op
), 1);
45 switch (child
->data_type
) {
48 fprintf(stderr
, "[error] Unknown root child data type\n");
51 fprintf(stderr
, "[error] String cannot be root data type\n");
54 case IR_DATA_FIELD_REF
:
60 op
->data_type
= child
->data_type
;
61 op
->signedness
= child
->signedness
;
62 op
->u
.root
.child
= child
;
67 struct ir_op
*make_op_load_string(char *string
, enum ir_side side
)
71 op
= calloc(sizeof(struct ir_op
), 1);
75 op
->data_type
= IR_DATA_STRING
;
76 op
->signedness
= IR_SIGN_UNKNOWN
;
78 op
->u
.load
.u
.string
= strdup(string
);
79 if (!op
->u
.load
.u
.string
) {
87 struct ir_op
*make_op_load_numeric(int64_t v
, enum ir_side side
)
91 op
= calloc(sizeof(struct ir_op
), 1);
95 op
->data_type
= IR_DATA_NUMERIC
;
96 /* TODO: for now, all numeric values are signed */
97 op
->signedness
= IR_SIGNED
;
104 struct ir_op
*make_op_load_field_ref(char *string
, enum ir_side side
)
108 op
= calloc(sizeof(struct ir_op
), 1);
112 op
->data_type
= IR_DATA_FIELD_REF
;
113 op
->signedness
= IR_SIGN_DYN
;
115 op
->u
.load
.u
.ref
= strdup(string
);
116 if (!op
->u
.load
.u
.ref
) {
124 struct ir_op
*make_op_unary(enum unary_op_type unary_op_type
,
125 const char *op_str
, enum ir_op_signedness signedness
,
126 struct ir_op
*child
, enum ir_side side
)
128 struct ir_op
*op
= NULL
;
130 if (child
->data_type
== IR_DATA_STRING
) {
131 fprintf(stderr
, "[error] unary operation '%s' not allowed on string literal\n", op_str
);
135 op
= calloc(sizeof(struct ir_op
), 1);
138 op
->op
= IR_OP_UNARY
;
139 op
->data_type
= child
->data_type
;
140 op
->signedness
= signedness
;
142 op
->u
.unary
.type
= unary_op_type
;
143 op
->u
.unary
.child
= child
;
152 * unary + is pretty much useless.
155 struct ir_op
*make_op_unary_plus(struct ir_op
*child
, enum ir_side side
)
157 return make_op_unary(AST_UNARY_PLUS
, "+", child
->signedness
,
162 struct ir_op
*make_op_unary_minus(struct ir_op
*child
, enum ir_side side
)
164 return make_op_unary(AST_UNARY_MINUS
, "-", child
->signedness
,
169 struct ir_op
*make_op_unary_not(struct ir_op
*child
, enum ir_side side
)
171 return make_op_unary(AST_UNARY_NOT
, "!", child
->signedness
,
177 struct ir_op
*make_op_binary_numeric(enum op_type bin_op_type
,
178 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
181 struct ir_op
*op
= NULL
;
183 if (right
->data_type
== IR_DATA_STRING
184 || right
->data_type
== IR_DATA_STRING
) {
185 fprintf(stderr
, "[error] binary operation '%s' not allowed on string literal\n", op_str
);
188 if (left
->data_type
== IR_DATA_UNKNOWN
189 || right
->data_type
== IR_DATA_UNKNOWN
) {
190 fprintf(stderr
, "[error] binary operation '%s' has unknown type for both children\n", op_str
);
195 op
= calloc(sizeof(struct ir_op_binary
), 1);
198 op
->op
= IR_OP_BINARY
;
199 op
->u
.binary
.type
= bin_op_type
;
200 op
->u
.binary
.left
= left
;
201 op
->u
.binary
.right
= right
;
205 * The field that is not a field ref will select type.
207 if (left
->data_type
!= IR_DATA_FIELD_REF
)
208 op
->data_type
= left
->data_type
;
210 op
->data_type
= right
->data_type
;
212 if (left
->signedness
== IR_SIGNED
213 || right
->signedness
== IR_SIGNED
) {
214 op
->signedness
= IR_SIGNED
;
215 } else if (left
->signedness
== IR_SIGN_DYN
216 || right
->signedness
== IR_SIGN_DYN
) {
217 op
->signedness
= IR_SIGN_DYN
;
218 } else if (left
->signedness
== IR_UNSIGNED
219 && right
->signedness
== IR_UNSIGNED
) {
220 op
->signedness
= IR_UNSIGNED
;
222 op
->signedness
= IR_SIGN_UNKNOWN
;
233 struct ir_op
*make_op_binary_mul(struct ir_op
*left
, struct ir_op
*right
,
236 return make_op_binary_numeric(AST_OP_MUL
, "*", left
, right
, side
);
240 struct ir_op
*make_op_binary_div(struct ir_op
*left
, struct ir_op
*right
,
243 return make_op_binary_numeric(AST_OP_DIV
, "/", left
, right
, side
);
247 struct ir_op
*make_op_binary_mod(struct ir_op
*left
, struct ir_op
*right
,
250 return make_op_binary_numeric(AST_OP_MOD
, "%", left
, right
, side
);
254 struct ir_op
*make_op_binary_plus(struct ir_op
*left
, struct ir_op
*right
,
257 return make_op_binary_numeric(AST_OP_PLUS
, "+", left
, right
, side
);
261 struct ir_op
*make_op_binary_minus(struct ir_op
*left
, struct ir_op
*right
,
264 return make_op_binary_numeric(AST_OP_MINUS
, "-", left
, right
, side
);
268 struct ir_op
*make_op_binary_rshift(struct ir_op
*left
, struct ir_op
*right
,
271 return make_op_binary_numeric(AST_OP_RSHIFT
, ">>", left
, right
, side
);
275 struct ir_op
*make_op_binary_lshift(struct ir_op
*left
, struct ir_op
*right
,
278 return make_op_binary_numeric(AST_OP_LSHIFT
, "<<", left
, right
, side
);
282 struct ir_op
*make_op_binary_and(struct ir_op
*left
, struct ir_op
*right
,
285 return make_op_binary_numeric(AST_OP_BIN_AND
, "&", left
, right
, side
);
289 struct ir_op
*make_op_binary_or(struct ir_op
*left
, struct ir_op
*right
,
292 return make_op_binary_numeric(AST_OP_BIN_OR
, "|", left
, right
, side
);
296 struct ir_op
*make_op_binary_xor(struct ir_op
*left
, struct ir_op
*right
,
299 return make_op_binary_numeric(AST_OP_BIN_XOR
, "^", left
, right
, side
);
304 struct ir_op
*make_op_binary_compare(enum op_type bin_op_type
,
305 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
308 struct ir_op
*op
= NULL
;
310 if (left
->data_type
== IR_DATA_UNKNOWN
311 || right
->data_type
== IR_DATA_UNKNOWN
) {
312 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
316 if ((left
->data_type
== IR_DATA_STRING
317 && right
->data_type
== IR_DATA_NUMERIC
)
318 || (left
->data_type
== IR_DATA_NUMERIC
&&
319 right
->data_type
== IR_DATA_STRING
)) {
320 fprintf(stderr
, "[error] binary operation '%s' operand type mismatch\n", op_str
);
324 op
= calloc(sizeof(struct ir_op
), 1);
327 op
->op
= IR_OP_BINARY
;
328 op
->u
.binary
.type
= bin_op_type
;
329 op
->u
.binary
.left
= left
;
330 op
->u
.binary
.right
= right
;
332 /* we return a boolean, represented as signed numeric */
333 op
->data_type
= IR_DATA_NUMERIC
;
334 op
->signedness
= IR_SIGNED
;
345 struct ir_op
*make_op_binary_eq(struct ir_op
*left
, struct ir_op
*right
,
348 return make_op_binary_compare(AST_OP_EQ
, "==", left
, right
, side
);
352 struct ir_op
*make_op_binary_ne(struct ir_op
*left
, struct ir_op
*right
,
355 return make_op_binary_compare(AST_OP_NE
, "!=", left
, right
, side
);
359 struct ir_op
*make_op_binary_gt(struct ir_op
*left
, struct ir_op
*right
,
362 return make_op_binary_compare(AST_OP_GT
, ">", left
, right
, side
);
366 struct ir_op
*make_op_binary_lt(struct ir_op
*left
, struct ir_op
*right
,
369 return make_op_binary_compare(AST_OP_LT
, "<", left
, right
, side
);
373 struct ir_op
*make_op_binary_ge(struct ir_op
*left
, struct ir_op
*right
,
376 return make_op_binary_compare(AST_OP_GE
, ">=", left
, right
, side
);
380 struct ir_op
*make_op_binary_le(struct ir_op
*left
, struct ir_op
*right
,
383 return make_op_binary_compare(AST_OP_LE
, "<=", left
, right
, side
);
387 struct ir_op
*make_op_binary_logical(enum op_type bin_op_type
,
388 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
391 struct ir_op
*op
= NULL
;
393 if (left
->data_type
== IR_DATA_UNKNOWN
394 || right
->data_type
== IR_DATA_UNKNOWN
) {
395 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
399 if (left
->data_type
== IR_DATA_STRING
400 || right
->data_type
== IR_DATA_STRING
) {
401 fprintf(stderr
, "[error] logical binary operation '%s' cannot have string operand\n", op_str
);
405 op
= calloc(sizeof(struct ir_op
), 1);
408 op
->op
= IR_OP_LOGICAL
;
409 op
->u
.binary
.type
= bin_op_type
;
410 op
->u
.binary
.left
= left
;
411 op
->u
.binary
.right
= right
;
413 /* we return a boolean, represented as signed numeric */
414 op
->data_type
= IR_DATA_NUMERIC
;
415 op
->signedness
= IR_SIGNED
;
426 struct ir_op
*make_op_binary_logical_and(struct ir_op
*left
, struct ir_op
*right
,
429 return make_op_binary_logical(AST_OP_AND
, "&&", left
, right
, side
);
433 struct ir_op
*make_op_binary_logical_or(struct ir_op
*left
, struct ir_op
*right
,
436 return make_op_binary_logical(AST_OP_OR
, "||", left
, right
, side
);
440 void filter_free_ir_recursive(struct ir_op
*op
)
447 fprintf(stderr
, "[error] Unknown op type in %s\n",
451 filter_free_ir_recursive(op
->u
.root
.child
);
454 switch (op
->data_type
) {
456 free(op
->u
.load
.u
.string
);
458 case IR_DATA_FIELD_REF
:
459 free(op
->u
.load
.u
.ref
);
466 filter_free_ir_recursive(op
->u
.unary
.child
);
469 filter_free_ir_recursive(op
->u
.binary
.left
);
470 filter_free_ir_recursive(op
->u
.binary
.right
);
473 filter_free_ir_recursive(op
->u
.logical
.left
);
474 filter_free_ir_recursive(op
->u
.logical
.right
);
481 struct ir_op
*make_expression(struct filter_parser_ctx
*ctx
,
482 struct filter_node
*node
, enum ir_side side
)
484 switch (node
->u
.expression
.type
) {
485 case AST_EXP_UNKNOWN
:
487 fprintf(stderr
, "[error] %s: unknown expression type\n", __func__
);
491 return make_op_load_string(node
->u
.expression
.u
.string
, side
);
492 case AST_EXP_CONSTANT
:
493 return make_op_load_numeric(node
->u
.expression
.u
.constant
,
495 case AST_EXP_IDENTIFIER
:
496 if (node
->u
.expression
.pre_op
!= AST_LINK_UNKNOWN
) {
497 fprintf(stderr
, "[error] %s: dotted and dereferenced identifiers not supported\n", __func__
);
500 return make_op_load_field_ref(node
->u
.expression
.u
.identifier
,
503 return generate_ir_recursive(ctx
, node
->u
.expression
.u
.child
,
509 struct ir_op
*make_op(struct filter_parser_ctx
*ctx
,
510 struct filter_node
*node
, enum ir_side side
)
512 struct ir_op
*op
= NULL
, *lchild
, *rchild
;
513 const char *op_str
= "?";
515 switch (node
->u
.op
.type
) {
518 fprintf(stderr
, "[error] %s: unknown binary op type\n", __func__
);
522 * Binary operators other than comparators and logical and/or
523 * are not supported. If we ever want to support those, we will
524 * need a stack for the general case rather than just 2
525 * registers (see bytecode).
529 goto error_not_supported
;
532 goto error_not_supported
;
535 goto error_not_supported
;
538 goto error_not_supported
;
541 goto error_not_supported
;
544 goto error_not_supported
;
547 goto error_not_supported
;
550 goto error_not_supported
;
553 goto error_not_supported
;
556 goto error_not_supported
;
564 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
567 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_RIGHT
);
569 filter_free_ir_recursive(lchild
);
577 * Both children considered as left, since we need to
580 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
583 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_LEFT
);
585 filter_free_ir_recursive(lchild
);
591 switch (node
->u
.op
.type
) {
593 op
= make_op_binary_logical_and(lchild
, rchild
, side
);
596 op
= make_op_binary_logical_or(lchild
, rchild
, side
);
599 op
= make_op_binary_eq(lchild
, rchild
, side
);
602 op
= make_op_binary_ne(lchild
, rchild
, side
);
605 op
= make_op_binary_gt(lchild
, rchild
, side
);
608 op
= make_op_binary_lt(lchild
, rchild
, side
);
611 op
= make_op_binary_ge(lchild
, rchild
, side
);
614 op
= make_op_binary_le(lchild
, rchild
, side
);
621 filter_free_ir_recursive(rchild
);
622 filter_free_ir_recursive(lchild
);
627 fprintf(stderr
, "[error] %s: binary operation '%s' not supported\n",
633 struct ir_op
*make_unary_op(struct filter_parser_ctx
*ctx
,
634 struct filter_node
*node
, enum ir_side side
)
636 switch (node
->u
.unary_op
.type
) {
637 case AST_UNARY_UNKNOWN
:
639 fprintf(stderr
, "[error] %s: unknown unary op type\n", __func__
);
644 struct ir_op
*op
, *child
;
646 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
650 op
= make_op_unary_plus(child
, side
);
652 filter_free_ir_recursive(child
);
657 case AST_UNARY_MINUS
:
659 struct ir_op
*op
, *child
;
661 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
665 op
= make_op_unary_minus(child
, side
);
667 filter_free_ir_recursive(child
);
674 struct ir_op
*op
, *child
;
676 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
680 op
= make_op_unary_not(child
, side
);
682 filter_free_ir_recursive(child
);
691 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
692 struct filter_node
*node
, enum ir_side side
)
694 switch (node
->type
) {
697 fprintf(stderr
, "[error] %s: unknown node type\n", __func__
);
702 struct ir_op
*op
, *child
;
704 child
= generate_ir_recursive(ctx
, node
->u
.root
.child
,
708 op
= make_op_root(child
, side
);
710 filter_free_ir_recursive(child
);
715 case NODE_EXPRESSION
:
716 return make_expression(ctx
, node
, side
);
718 return make_op(ctx
, node
, side
);
720 return make_unary_op(ctx
, node
, side
);
726 void filter_ir_free(struct filter_parser_ctx
*ctx
)
728 filter_free_ir_recursive(ctx
->ir_root
);
732 int filter_visitor_ir_generate(struct filter_parser_ctx
*ctx
)
736 op
= generate_ir_recursive(ctx
, &ctx
->ast
->root
, IR_LEFT
);