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-ast.h"
30 #include "filter-parser.h"
31 #include "filter-ir.h"
33 #include <common/macros.h>
36 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
37 struct filter_node
*node
, enum ir_side side
);
40 struct ir_op
*make_op_root(struct ir_op
*child
, enum ir_side side
)
44 op
= calloc(sizeof(struct ir_op
), 1);
47 switch (child
->data_type
) {
50 fprintf(stderr
, "[error] Unknown root child data type\n");
54 fprintf(stderr
, "[error] String cannot be root data type\n");
58 case IR_DATA_FIELD_REF
:
59 case IR_DATA_GET_CONTEXT_REF
:
65 op
->data_type
= child
->data_type
;
66 op
->signedness
= child
->signedness
;
67 op
->u
.root
.child
= child
;
72 struct ir_op
*make_op_load_string(char *string
, enum ir_side side
)
76 op
= calloc(sizeof(struct ir_op
), 1);
80 op
->data_type
= IR_DATA_STRING
;
81 op
->signedness
= IR_SIGN_UNKNOWN
;
83 op
->u
.load
.u
.string
= strdup(string
);
84 if (!op
->u
.load
.u
.string
) {
92 struct ir_op
*make_op_load_numeric(int64_t v
, enum ir_side side
)
96 op
= calloc(sizeof(struct ir_op
), 1);
100 op
->data_type
= IR_DATA_NUMERIC
;
101 /* TODO: for now, all numeric values are signed */
102 op
->signedness
= IR_SIGNED
;
104 op
->u
.load
.u
.num
= v
;
109 struct ir_op
*make_op_load_float(double v
, enum ir_side side
)
113 op
= calloc(sizeof(struct ir_op
), 1);
117 op
->data_type
= IR_DATA_FLOAT
;
118 op
->signedness
= IR_SIGN_UNKNOWN
;
120 op
->u
.load
.u
.flt
= v
;
125 struct ir_op
*make_op_load_field_ref(char *string
, enum ir_side side
)
129 op
= calloc(sizeof(struct ir_op
), 1);
133 op
->data_type
= IR_DATA_FIELD_REF
;
134 op
->signedness
= IR_SIGN_DYN
;
136 op
->u
.load
.u
.ref
= strdup(string
);
137 if (!op
->u
.load
.u
.ref
) {
145 struct ir_op
*make_op_load_get_context_ref(char *string
, enum ir_side side
)
149 op
= calloc(sizeof(struct ir_op
), 1);
153 op
->data_type
= IR_DATA_GET_CONTEXT_REF
;
154 op
->signedness
= IR_SIGN_DYN
;
156 op
->u
.load
.u
.ref
= strdup(string
);
157 if (!op
->u
.load
.u
.ref
) {
165 struct ir_op
*make_op_unary(enum unary_op_type unary_op_type
,
166 const char *op_str
, enum ir_op_signedness signedness
,
167 struct ir_op
*child
, enum ir_side side
)
169 struct ir_op
*op
= NULL
;
171 if (child
->data_type
== IR_DATA_STRING
) {
172 fprintf(stderr
, "[error] unary operation '%s' not allowed on string literal\n", op_str
);
176 op
= calloc(sizeof(struct ir_op
), 1);
179 op
->op
= IR_OP_UNARY
;
180 op
->data_type
= child
->data_type
;
181 op
->signedness
= signedness
;
183 op
->u
.unary
.type
= unary_op_type
;
184 op
->u
.unary
.child
= child
;
193 * unary + is pretty much useless.
196 struct ir_op
*make_op_unary_plus(struct ir_op
*child
, enum ir_side side
)
198 return make_op_unary(AST_UNARY_PLUS
, "+", child
->signedness
,
203 struct ir_op
*make_op_unary_minus(struct ir_op
*child
, enum ir_side side
)
205 return make_op_unary(AST_UNARY_MINUS
, "-", child
->signedness
,
210 struct ir_op
*make_op_unary_not(struct ir_op
*child
, enum ir_side side
)
212 return make_op_unary(AST_UNARY_NOT
, "!", child
->signedness
,
218 struct ir_op
*make_op_binary_numeric(enum op_type bin_op_type
,
219 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
222 struct ir_op
*op
= NULL
;
224 if (right
->data_type
== IR_DATA_STRING
225 || right
->data_type
== IR_DATA_STRING
) {
226 fprintf(stderr
, "[error] binary operation '%s' not allowed on string literal\n", op_str
);
229 if (left
->data_type
== IR_DATA_UNKNOWN
230 || right
->data_type
== IR_DATA_UNKNOWN
) {
231 fprintf(stderr
, "[error] binary operation '%s' has unknown type for both children\n", op_str
);
236 op
= calloc(sizeof(struct ir_op_binary
), 1);
239 op
->op
= IR_OP_BINARY
;
240 op
->u
.binary
.type
= bin_op_type
;
241 op
->u
.binary
.left
= left
;
242 op
->u
.binary
.right
= right
;
246 * The field that is not a field ref will select type.
248 if (left
->data_type
!= IR_DATA_FIELD_REF
249 && left
->data_type
!= IR_DATA_GET_CONTEXT_REF
)
250 op
->data_type
= left
->data_type
;
252 op
->data_type
= right
->data_type
;
254 if (left
->signedness
== IR_SIGNED
255 || right
->signedness
== IR_SIGNED
) {
256 op
->signedness
= IR_SIGNED
;
257 } else if (left
->signedness
== IR_SIGN_DYN
258 || right
->signedness
== IR_SIGN_DYN
) {
259 op
->signedness
= IR_SIGN_DYN
;
260 } else if (left
->signedness
== IR_UNSIGNED
261 && right
->signedness
== IR_UNSIGNED
) {
262 op
->signedness
= IR_UNSIGNED
;
264 op
->signedness
= IR_SIGN_UNKNOWN
;
275 struct ir_op
*make_op_binary_mul(struct ir_op
*left
, struct ir_op
*right
,
278 return make_op_binary_numeric(AST_OP_MUL
, "*", left
, right
, side
);
282 struct ir_op
*make_op_binary_div(struct ir_op
*left
, struct ir_op
*right
,
285 return make_op_binary_numeric(AST_OP_DIV
, "/", left
, right
, side
);
289 struct ir_op
*make_op_binary_mod(struct ir_op
*left
, struct ir_op
*right
,
292 return make_op_binary_numeric(AST_OP_MOD
, "%", left
, right
, side
);
296 struct ir_op
*make_op_binary_plus(struct ir_op
*left
, struct ir_op
*right
,
299 return make_op_binary_numeric(AST_OP_PLUS
, "+", left
, right
, side
);
303 struct ir_op
*make_op_binary_minus(struct ir_op
*left
, struct ir_op
*right
,
306 return make_op_binary_numeric(AST_OP_MINUS
, "-", left
, right
, side
);
310 struct ir_op
*make_op_binary_rshift(struct ir_op
*left
, struct ir_op
*right
,
313 return make_op_binary_numeric(AST_OP_RSHIFT
, ">>", left
, right
, side
);
317 struct ir_op
*make_op_binary_lshift(struct ir_op
*left
, struct ir_op
*right
,
320 return make_op_binary_numeric(AST_OP_LSHIFT
, "<<", left
, right
, side
);
324 struct ir_op
*make_op_binary_and(struct ir_op
*left
, struct ir_op
*right
,
327 return make_op_binary_numeric(AST_OP_BIN_AND
, "&", left
, right
, side
);
331 struct ir_op
*make_op_binary_or(struct ir_op
*left
, struct ir_op
*right
,
334 return make_op_binary_numeric(AST_OP_BIN_OR
, "|", left
, right
, side
);
338 struct ir_op
*make_op_binary_xor(struct ir_op
*left
, struct ir_op
*right
,
341 return make_op_binary_numeric(AST_OP_BIN_XOR
, "^", left
, right
, side
);
346 struct ir_op
*make_op_binary_compare(enum op_type bin_op_type
,
347 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
350 struct ir_op
*op
= NULL
;
352 if (left
->data_type
== IR_DATA_UNKNOWN
353 || right
->data_type
== IR_DATA_UNKNOWN
) {
354 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
358 if ((left
->data_type
== IR_DATA_STRING
359 && (right
->data_type
== IR_DATA_NUMERIC
|| right
->data_type
== IR_DATA_FLOAT
))
360 || ((left
->data_type
== IR_DATA_NUMERIC
|| left
->data_type
== IR_DATA_FLOAT
) &&
361 right
->data_type
== IR_DATA_STRING
)) {
362 fprintf(stderr
, "[error] binary operation '%s' operand type mismatch\n", op_str
);
366 op
= calloc(sizeof(struct ir_op
), 1);
369 op
->op
= IR_OP_BINARY
;
370 op
->u
.binary
.type
= bin_op_type
;
371 op
->u
.binary
.left
= left
;
372 op
->u
.binary
.right
= right
;
374 /* we return a boolean, represented as signed numeric */
375 op
->data_type
= IR_DATA_NUMERIC
;
376 op
->signedness
= IR_SIGNED
;
387 struct ir_op
*make_op_binary_eq(struct ir_op
*left
, struct ir_op
*right
,
390 return make_op_binary_compare(AST_OP_EQ
, "==", left
, right
, side
);
394 struct ir_op
*make_op_binary_ne(struct ir_op
*left
, struct ir_op
*right
,
397 return make_op_binary_compare(AST_OP_NE
, "!=", left
, right
, side
);
401 struct ir_op
*make_op_binary_gt(struct ir_op
*left
, struct ir_op
*right
,
404 return make_op_binary_compare(AST_OP_GT
, ">", left
, right
, side
);
408 struct ir_op
*make_op_binary_lt(struct ir_op
*left
, struct ir_op
*right
,
411 return make_op_binary_compare(AST_OP_LT
, "<", left
, right
, side
);
415 struct ir_op
*make_op_binary_ge(struct ir_op
*left
, struct ir_op
*right
,
418 return make_op_binary_compare(AST_OP_GE
, ">=", left
, right
, side
);
422 struct ir_op
*make_op_binary_le(struct ir_op
*left
, struct ir_op
*right
,
425 return make_op_binary_compare(AST_OP_LE
, "<=", left
, right
, side
);
429 struct ir_op
*make_op_binary_logical(enum op_type bin_op_type
,
430 const char *op_str
, struct ir_op
*left
, struct ir_op
*right
,
433 struct ir_op
*op
= NULL
;
435 if (left
->data_type
== IR_DATA_UNKNOWN
436 || right
->data_type
== IR_DATA_UNKNOWN
) {
437 fprintf(stderr
, "[error] binary operation '%s' has unknown operand type\n", op_str
);
441 if (left
->data_type
== IR_DATA_STRING
442 || right
->data_type
== IR_DATA_STRING
) {
443 fprintf(stderr
, "[error] logical binary operation '%s' cannot have string operand\n", op_str
);
447 op
= calloc(sizeof(struct ir_op
), 1);
450 op
->op
= IR_OP_LOGICAL
;
451 op
->u
.binary
.type
= bin_op_type
;
452 op
->u
.binary
.left
= left
;
453 op
->u
.binary
.right
= right
;
455 /* we return a boolean, represented as signed numeric */
456 op
->data_type
= IR_DATA_NUMERIC
;
457 op
->signedness
= IR_SIGNED
;
468 struct ir_op
*make_op_binary_logical_and(struct ir_op
*left
, struct ir_op
*right
,
471 return make_op_binary_logical(AST_OP_AND
, "&&", left
, right
, side
);
475 struct ir_op
*make_op_binary_logical_or(struct ir_op
*left
, struct ir_op
*right
,
478 return make_op_binary_logical(AST_OP_OR
, "||", left
, right
, side
);
482 void filter_free_ir_recursive(struct ir_op
*op
)
489 fprintf(stderr
, "[error] Unknown op type in %s\n",
493 filter_free_ir_recursive(op
->u
.root
.child
);
496 switch (op
->data_type
) {
498 free(op
->u
.load
.u
.string
);
500 case IR_DATA_FIELD_REF
: /* fall-through */
501 case IR_DATA_GET_CONTEXT_REF
:
502 free(op
->u
.load
.u
.ref
);
509 filter_free_ir_recursive(op
->u
.unary
.child
);
512 filter_free_ir_recursive(op
->u
.binary
.left
);
513 filter_free_ir_recursive(op
->u
.binary
.right
);
516 filter_free_ir_recursive(op
->u
.logical
.left
);
517 filter_free_ir_recursive(op
->u
.logical
.right
);
524 struct ir_op
*make_expression(struct filter_parser_ctx
*ctx
,
525 struct filter_node
*node
, enum ir_side side
)
527 switch (node
->u
.expression
.type
) {
528 case AST_EXP_UNKNOWN
:
530 fprintf(stderr
, "[error] %s: unknown expression type\n", __func__
);
534 return make_op_load_string(node
->u
.expression
.u
.string
, side
);
535 case AST_EXP_CONSTANT
:
536 return make_op_load_numeric(node
->u
.expression
.u
.constant
,
538 case AST_EXP_FLOAT_CONSTANT
:
539 return make_op_load_float(node
->u
.expression
.u
.float_constant
,
541 case AST_EXP_IDENTIFIER
:
542 if (node
->u
.expression
.pre_op
!= AST_LINK_UNKNOWN
) {
543 fprintf(stderr
, "[error] %s: dotted and dereferenced identifiers not supported\n", __func__
);
546 return make_op_load_field_ref(node
->u
.expression
.u
.identifier
,
548 case AST_EXP_GLOBAL_IDENTIFIER
:
550 struct filter_node
*next
;
552 if (node
->u
.expression
.pre_op
== AST_LINK_UNKNOWN
) {
553 fprintf(stderr
, "[error] %s: global identifiers need chained identifier \n", __func__
);
556 /* We currently only support $ctx (context) identifiers */
557 if (strncmp(node
->u
.expression
.u
.identifier
,
558 "$ctx", strlen("$ctx")) != 0) {
559 fprintf(stderr
, "[error] %s: \"%s\" global identifier is unknown. Only \"$ctx\" currently implemented.\n", __func__
, node
->u
.expression
.u
.identifier
);
562 next
= node
->u
.expression
.next
;
564 fprintf(stderr
, "[error] %s: Expecting a context name, e.g. \'$ctx.name\'.\n", __func__
);
567 if (next
->type
!= NODE_EXPRESSION
) {
568 fprintf(stderr
, "[error] %s: Expecting expression.\n", __func__
);
571 if (next
->u
.expression
.type
!= AST_EXP_IDENTIFIER
) {
572 fprintf(stderr
, "[error] %s: Expecting identifier.\n", __func__
);
575 if (next
->u
.expression
.pre_op
!= AST_LINK_UNKNOWN
) {
576 fprintf(stderr
, "[error] %s: dotted and dereferenced identifiers not supported after identifier\n", __func__
);
579 return make_op_load_get_context_ref(next
->u
.expression
.u
.identifier
,
583 return generate_ir_recursive(ctx
, node
->u
.expression
.u
.child
,
589 struct ir_op
*make_op(struct filter_parser_ctx
*ctx
,
590 struct filter_node
*node
, enum ir_side side
)
592 struct ir_op
*op
= NULL
, *lchild
, *rchild
;
593 const char *op_str
= "?";
595 switch (node
->u
.op
.type
) {
598 fprintf(stderr
, "[error] %s: unknown binary op type\n", __func__
);
602 * Binary operators other than comparators and logical and/or
603 * are not supported. If we ever want to support those, we will
604 * need a stack for the general case rather than just 2
605 * registers (see bytecode).
609 goto error_not_supported
;
612 goto error_not_supported
;
615 goto error_not_supported
;
618 goto error_not_supported
;
621 goto error_not_supported
;
624 goto error_not_supported
;
627 goto error_not_supported
;
630 goto error_not_supported
;
633 goto error_not_supported
;
636 goto error_not_supported
;
644 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
647 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_RIGHT
);
649 filter_free_ir_recursive(lchild
);
657 * Both children considered as left, since we need to
660 lchild
= generate_ir_recursive(ctx
, node
->u
.op
.lchild
, IR_LEFT
);
663 rchild
= generate_ir_recursive(ctx
, node
->u
.op
.rchild
, IR_LEFT
);
665 filter_free_ir_recursive(lchild
);
671 switch (node
->u
.op
.type
) {
673 op
= make_op_binary_logical_and(lchild
, rchild
, side
);
676 op
= make_op_binary_logical_or(lchild
, rchild
, side
);
679 op
= make_op_binary_eq(lchild
, rchild
, side
);
682 op
= make_op_binary_ne(lchild
, rchild
, side
);
685 op
= make_op_binary_gt(lchild
, rchild
, side
);
688 op
= make_op_binary_lt(lchild
, rchild
, side
);
691 op
= make_op_binary_ge(lchild
, rchild
, side
);
694 op
= make_op_binary_le(lchild
, rchild
, side
);
701 filter_free_ir_recursive(rchild
);
702 filter_free_ir_recursive(lchild
);
707 fprintf(stderr
, "[error] %s: binary operation '%s' not supported\n",
713 struct ir_op
*make_unary_op(struct filter_parser_ctx
*ctx
,
714 struct filter_node
*node
, enum ir_side side
)
716 const char *op_str
= "?";
718 switch (node
->u
.unary_op
.type
) {
719 case AST_UNARY_UNKNOWN
:
721 fprintf(stderr
, "[error] %s: unknown unary op type\n", __func__
);
726 struct ir_op
*op
, *child
;
728 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
732 op
= make_op_unary_plus(child
, side
);
734 filter_free_ir_recursive(child
);
739 case AST_UNARY_MINUS
:
741 struct ir_op
*op
, *child
;
743 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
747 op
= make_op_unary_minus(child
, side
);
749 filter_free_ir_recursive(child
);
756 struct ir_op
*op
, *child
;
758 child
= generate_ir_recursive(ctx
, node
->u
.unary_op
.child
,
762 op
= make_op_unary_not(child
, side
);
764 filter_free_ir_recursive(child
);
769 case AST_UNARY_BIN_NOT
:
772 goto error_not_supported
;
777 fprintf(stderr
, "[error] %s: unary operation '%s' not supported\n",
783 struct ir_op
*generate_ir_recursive(struct filter_parser_ctx
*ctx
,
784 struct filter_node
*node
, enum ir_side side
)
786 switch (node
->type
) {
789 fprintf(stderr
, "[error] %s: unknown node type\n", __func__
);
794 struct ir_op
*op
, *child
;
796 child
= generate_ir_recursive(ctx
, node
->u
.root
.child
,
800 op
= make_op_root(child
, side
);
802 filter_free_ir_recursive(child
);
807 case NODE_EXPRESSION
:
808 return make_expression(ctx
, node
, side
);
810 return make_op(ctx
, node
, side
);
812 return make_unary_op(ctx
, node
, side
);
818 void filter_ir_free(struct filter_parser_ctx
*ctx
)
820 filter_free_ir_recursive(ctx
->ir_root
);
825 int filter_visitor_ir_generate(struct filter_parser_ctx
*ctx
)
829 op
= generate_ir_recursive(ctx
, &ctx
->ast
->root
, IR_LEFT
);