1 /* A simple stack-based virtual machine to demonstrate
3 Copyright (C) 2014-2017 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
29 #include <libgccjit.h>
32 typedef struct toyvm_op toyvm_op
;
33 typedef struct toyvm_function toyvm_function
;
34 typedef struct toyvm_frame toyvm_frame
;
35 typedef struct compilation_state compilation_state
;
36 typedef struct toyvm_compiled_function toyvm_compiled_function
;
38 /* Functions are compiled to this function ptr type. */
39 typedef int (*toyvm_compiled_code
) (int);
42 /* Ops taking no operand. */
52 /* Ops taking an operand. */
57 #define FIRST_UNARY_OPCODE (PUSH_CONST)
59 const char * const opcode_names
[] = {
75 /* Which operation. */
76 enum opcode op_opcode
;
78 /* Some opcodes take an argument. */
81 /* The line number of the operation within the source file. */
89 const char *fn_filename
;
91 toyvm_op fn_ops
[MAX_OPS
];
94 #define MAX_STACK_DEPTH (8)
98 toyvm_function
*frm_function
;
100 int frm_stack
[MAX_STACK_DEPTH
];
105 add_op (toyvm_function
*fn
, enum opcode opcode
,
106 int operand
, int linenum
)
109 assert (fn
->fn_num_ops
< MAX_OPS
);
110 op
= &fn
->fn_ops
[fn
->fn_num_ops
++];
111 op
->op_opcode
= opcode
;
112 op
->op_operand
= operand
;
113 op
->op_linenum
= linenum
;
117 add_unary_op (toyvm_function
*fn
, enum opcode opcode
,
118 const char *rest_of_line
, int linenum
)
120 int operand
= atoi (rest_of_line
);
121 add_op (fn
, opcode
, operand
, linenum
);
125 get_function_name (const char *filename
)
127 /* Skip any path separators. */
128 const char *pathsep
= strrchr (filename
, '/');
130 filename
= pathsep
+ 1;
132 /* Copy filename to funcname. */
133 char *funcname
= (char *)malloc (strlen (filename
) + 1);
135 strcpy (funcname
, filename
);
137 /* Convert "." to NIL terminator. */
138 *(strchr (funcname
, '.')) = '\0';
143 static toyvm_function
*
144 toyvm_function_parse (const char *filename
, const char *name
)
147 toyvm_function
*fn
= NULL
;
156 f
= fopen (filename
, "r");
160 "cannot open file %s: %s\n",
161 filename
, strerror (errno
));
165 fn
= (toyvm_function
*)calloc (1, sizeof (toyvm_function
));
168 fprintf (stderr
, "out of memory allocating toyvm_function\n");
171 fn
->fn_filename
= filename
;
173 /* Read the lines of the file. */
174 while ((linelen
= getline (&line
, &bufsize
, f
)) != -1)
176 /* Note that this is a terrible parser, but it avoids the need to
177 bring in lex/yacc as a dependency. */
181 fprintf (stdout
, "%3d: %s", linenum
, line
);
183 /* Lines beginning with # are comments. */
187 /* Skip blank lines. */
191 #define LINE_MATCHES(OPCODE) (0 == strncmp ((OPCODE), line, strlen (OPCODE)))
192 if (LINE_MATCHES ("DUP\n"))
193 add_op (fn
, DUP
, 0, linenum
);
194 else if (LINE_MATCHES ("ROT\n"))
195 add_op (fn
, ROT
, 0, linenum
);
196 else if (LINE_MATCHES ("BINARY_ADD\n"))
197 add_op (fn
, BINARY_ADD
, 0, linenum
);
198 else if (LINE_MATCHES ("BINARY_SUBTRACT\n"))
199 add_op (fn
, BINARY_SUBTRACT
, 0, linenum
);
200 else if (LINE_MATCHES ("BINARY_MULT\n"))
201 add_op (fn
, BINARY_MULT
, 0, linenum
);
202 else if (LINE_MATCHES ("BINARY_COMPARE_LT\n"))
203 add_op (fn
, BINARY_COMPARE_LT
, 0, linenum
);
204 else if (LINE_MATCHES ("RECURSE\n"))
205 add_op (fn
, RECURSE
, 0, linenum
);
206 else if (LINE_MATCHES ("RETURN\n"))
207 add_op (fn
, RETURN
, 0, linenum
);
208 else if (LINE_MATCHES ("PUSH_CONST "))
209 add_unary_op (fn
, PUSH_CONST
,
210 line
+ strlen ("PUSH_CONST "), linenum
);
211 else if (LINE_MATCHES ("JUMP_ABS_IF_TRUE "))
212 add_unary_op (fn
, JUMP_ABS_IF_TRUE
,
213 line
+ strlen("JUMP_ABS_IF_TRUE "), linenum
);
216 fprintf (stderr
, "%s:%d: parse error\n", filename
, linenum
);
237 toyvm_function_disassemble_op (toyvm_function
*fn
, toyvm_op
*op
, int index
, FILE *out
)
239 fprintf (out
, "%s:%d: index %d: %s",
240 fn
->fn_filename
, op
->op_linenum
, index
,
241 opcode_names
[op
->op_opcode
]);
242 if (op
->op_opcode
>= FIRST_UNARY_OPCODE
)
243 fprintf (out
, " %d", op
->op_operand
);
248 toyvm_function_disassemble (toyvm_function
*fn
, FILE *out
)
251 for (i
= 0; i
< fn
->fn_num_ops
; i
++)
253 toyvm_op
*op
= &fn
->fn_ops
[i
];
254 toyvm_function_disassemble_op (fn
, op
, i
, out
);
259 toyvm_frame_push (toyvm_frame
*frame
, int arg
)
261 assert (frame
->frm_cur_depth
< MAX_STACK_DEPTH
);
262 frame
->frm_stack
[frame
->frm_cur_depth
++] = arg
;
266 toyvm_frame_pop (toyvm_frame
*frame
)
268 assert (frame
->frm_cur_depth
> 0);
269 return frame
->frm_stack
[--frame
->frm_cur_depth
];
273 toyvm_frame_dump_stack (toyvm_frame
*frame
, FILE *out
)
276 fprintf (out
, "stack:");
277 for (i
= 0; i
< frame
->frm_cur_depth
; i
++)
279 fprintf (out
, " %d", frame
->frm_stack
[i
]);
284 /* Execute the given function. */
287 toyvm_function_interpret (toyvm_function
*fn
, int arg
, FILE *trace
)
290 #define PUSH(ARG) (toyvm_frame_push (&frame, (ARG)))
291 #define POP(ARG) (toyvm_frame_pop (&frame))
293 frame
.frm_function
= fn
;
295 frame
.frm_cur_depth
= 0;
303 assert (frame
.frm_pc
< fn
->fn_num_ops
);
304 op
= &fn
->fn_ops
[frame
.frm_pc
++];
308 toyvm_frame_dump_stack (&frame
, trace
);
309 toyvm_function_disassemble_op (fn
, op
, frame
.frm_pc
, trace
);
312 switch (op
->op_opcode
)
314 /* Ops taking no operand. */
334 case BINARY_SUBTRACT
:
346 case BINARY_COMPARE_LT
:
354 x
= toyvm_function_interpret (fn
, x
, trace
);
361 /* Ops taking an operand. */
363 PUSH (op
->op_operand
);
366 case JUMP_ABS_IF_TRUE
:
369 frame
.frm_pc
= op
->op_operand
;
373 assert (0); /* unknown opcode */
375 } /* end of switch on opcode */
376 } /* end of while loop */
382 /* JIT compilation. */
384 struct compilation_state
386 gcc_jit_context
*ctxt
;
388 gcc_jit_type
*int_type
;
389 gcc_jit_type
*bool_type
;
390 gcc_jit_type
*stack_type
; /* int[MAX_STACK_DEPTH] */
392 gcc_jit_rvalue
*const_one
;
394 gcc_jit_function
*fn
;
395 gcc_jit_param
*param_arg
;
396 gcc_jit_lvalue
*stack
;
397 gcc_jit_lvalue
*stack_depth
;
401 gcc_jit_location
*op_locs
[MAX_OPS
];
402 gcc_jit_block
*initial_block
;
403 gcc_jit_block
*op_blocks
[MAX_OPS
];
407 /* Stack manipulation. */
410 add_push (compilation_state
*state
,
411 gcc_jit_block
*block
,
412 gcc_jit_rvalue
*rvalue
,
413 gcc_jit_location
*loc
)
415 /* stack[stack_depth] = RVALUE */
416 gcc_jit_block_add_assignment (
419 /* stack[stack_depth] */
420 gcc_jit_context_new_array_access (
423 gcc_jit_lvalue_as_rvalue (state
->stack
),
424 gcc_jit_lvalue_as_rvalue (state
->stack_depth
)),
427 /* "stack_depth++;". */
428 gcc_jit_block_add_assignment_op (
432 GCC_JIT_BINARY_OP_PLUS
,
437 add_pop (compilation_state
*state
,
438 gcc_jit_block
*block
,
439 gcc_jit_lvalue
*lvalue
,
440 gcc_jit_location
*loc
)
442 /* "--stack_depth;". */
443 gcc_jit_block_add_assignment_op (
447 GCC_JIT_BINARY_OP_MINUS
,
450 /* "LVALUE = stack[stack_depth];". */
451 gcc_jit_block_add_assignment (
455 /* stack[stack_depth] */
456 gcc_jit_lvalue_as_rvalue (
457 gcc_jit_context_new_array_access (
460 gcc_jit_lvalue_as_rvalue (state
->stack
),
461 gcc_jit_lvalue_as_rvalue (state
->stack_depth
))));
464 /* A struct to hold the compilation results. */
466 struct toyvm_compiled_function
468 gcc_jit_result
*cf_jit_result
;
469 toyvm_compiled_code cf_code
;
472 /* The main compilation hook. */
474 static toyvm_compiled_function
*
475 toyvm_function_compile (toyvm_function
*fn
)
477 compilation_state state
;
481 memset (&state
, 0, sizeof (state
));
483 funcname
= get_function_name (fn
->fn_filename
);
485 state
.ctxt
= gcc_jit_context_acquire ();
487 gcc_jit_context_set_bool_option (state
.ctxt
,
488 GCC_JIT_BOOL_OPTION_DUMP_INITIAL_GIMPLE
,
490 gcc_jit_context_set_bool_option (state
.ctxt
,
491 GCC_JIT_BOOL_OPTION_DUMP_GENERATED_CODE
,
493 gcc_jit_context_set_int_option (state
.ctxt
,
494 GCC_JIT_INT_OPTION_OPTIMIZATION_LEVEL
,
496 gcc_jit_context_set_bool_option (state
.ctxt
,
497 GCC_JIT_BOOL_OPTION_KEEP_INTERMEDIATES
,
499 gcc_jit_context_set_bool_option (state
.ctxt
,
500 GCC_JIT_BOOL_OPTION_DUMP_EVERYTHING
,
502 gcc_jit_context_set_bool_option (state
.ctxt
,
503 GCC_JIT_BOOL_OPTION_DEBUGINFO
,
508 gcc_jit_context_get_type (state
.ctxt
, GCC_JIT_TYPE_INT
);
510 gcc_jit_context_get_type (state
.ctxt
, GCC_JIT_TYPE_BOOL
);
512 gcc_jit_context_new_array_type (state
.ctxt
, NULL
,
513 state
.int_type
, MAX_STACK_DEPTH
);
515 /* The constant value 1. */
516 state
.const_one
= gcc_jit_context_one (state
.ctxt
, state
.int_type
);
518 /* Create locations. */
519 for (pc
= 0; pc
< fn
->fn_num_ops
; pc
++)
521 toyvm_op
*op
= &fn
->fn_ops
[pc
];
523 state
.op_locs
[pc
] = gcc_jit_context_new_location (state
.ctxt
,
529 /* Creating the function. */
531 gcc_jit_context_new_param (state
.ctxt
, state
.op_locs
[0],
532 state
.int_type
, "arg");
534 gcc_jit_context_new_function (state
.ctxt
,
536 GCC_JIT_FUNCTION_EXPORTED
,
539 1, &state
.param_arg
, 0);
541 /* Create stack lvalues. */
543 gcc_jit_function_new_local (state
.fn
, NULL
,
544 state
.stack_type
, "stack");
546 gcc_jit_function_new_local (state
.fn
, NULL
,
547 state
.int_type
, "stack_depth");
549 gcc_jit_function_new_local (state
.fn
, NULL
,
550 state
.int_type
, "x");
552 gcc_jit_function_new_local (state
.fn
, NULL
,
553 state
.int_type
, "y");
555 /* 1st pass: create blocks, one per opcode. */
557 /* We need an entry block to do one-time initialization, so create that
559 state
.initial_block
= gcc_jit_function_new_block (state
.fn
, "initial");
561 /* Create a block per operation. */
562 for (pc
= 0; pc
< fn
->fn_num_ops
; pc
++)
565 sprintf (buf
, "instr%i", pc
);
566 state
.op_blocks
[pc
] = gcc_jit_function_new_block (state
.fn
, buf
);
569 /* Populate the initial block. */
571 /* "stack_depth = 0;". */
572 gcc_jit_block_add_assignment (
576 gcc_jit_context_zero (state
.ctxt
, state
.int_type
));
581 gcc_jit_param_as_rvalue (state
.param_arg
),
584 /* ...and jump to insn 0. */
585 gcc_jit_block_end_with_jump (state
.initial_block
,
589 /* 2nd pass: fill in instructions. */
590 for (pc
= 0; pc
< fn
->fn_num_ops
; pc
++)
592 gcc_jit_location
*loc
= state
.op_locs
[pc
];
594 gcc_jit_block
*block
= state
.op_blocks
[pc
];
595 gcc_jit_block
*next_block
= (pc
< fn
->fn_num_ops
596 ? state
.op_blocks
[pc
+ 1]
600 op
= &fn
->fn_ops
[pc
];
604 #define X_EQUALS_POP()\
605 add_pop (&state, block, state.x, loc)
606 #define Y_EQUALS_POP()\
607 add_pop (&state, block, state.y, loc)
608 #define PUSH_RVALUE(RVALUE)\
609 add_push (&state, block, (RVALUE), loc)
611 PUSH_RVALUE (gcc_jit_lvalue_as_rvalue (state.x))
613 PUSH_RVALUE (gcc_jit_lvalue_as_rvalue (state.y))
615 gcc_jit_block_add_comment (block
, loc
, opcode_names
[op
->op_opcode
]);
617 /* Handle the individual opcodes. */
619 switch (op
->op_opcode
)
638 gcc_jit_context_new_binary_op (
641 GCC_JIT_BINARY_OP_PLUS
,
643 gcc_jit_lvalue_as_rvalue (state
.x
),
644 gcc_jit_lvalue_as_rvalue (state
.y
)));
647 case BINARY_SUBTRACT
:
651 gcc_jit_context_new_binary_op (
654 GCC_JIT_BINARY_OP_MINUS
,
656 gcc_jit_lvalue_as_rvalue (state
.x
),
657 gcc_jit_lvalue_as_rvalue (state
.y
)));
664 gcc_jit_context_new_binary_op (
667 GCC_JIT_BINARY_OP_MULT
,
669 gcc_jit_lvalue_as_rvalue (state
.x
),
670 gcc_jit_lvalue_as_rvalue (state
.y
)));
673 case BINARY_COMPARE_LT
:
677 /* cast of bool to int */
678 gcc_jit_context_new_cast (
681 /* (x < y) as a bool */
682 gcc_jit_context_new_comparison (
685 GCC_JIT_COMPARISON_LT
,
686 gcc_jit_lvalue_as_rvalue (state
.x
),
687 gcc_jit_lvalue_as_rvalue (state
.y
)),
694 gcc_jit_rvalue
*arg
= gcc_jit_lvalue_as_rvalue (state
.x
);
696 gcc_jit_context_new_call (
706 gcc_jit_block_end_with_return (
709 gcc_jit_lvalue_as_rvalue (state
.x
));
712 /* Ops taking an operand. */
715 gcc_jit_context_new_rvalue_from_int (
721 case JUMP_ABS_IF_TRUE
:
723 gcc_jit_block_end_with_conditional (
727 gcc_jit_context_new_cast (
730 gcc_jit_lvalue_as_rvalue (state
.x
),
732 state
.op_blocks
[op
->op_operand
], /* on_true */
733 next_block
); /* on_false */
738 } /* end of switch on opcode */
740 /* Go to the next block. */
741 if (op
->op_opcode
!= JUMP_ABS_IF_TRUE
742 && op
->op_opcode
!= RETURN
)
743 gcc_jit_block_end_with_jump (
748 } /* end of loop on PC locations. */
750 /* We've now finished populating the context. Compile it. */
751 gcc_jit_result
*jit_result
= gcc_jit_context_compile (state
.ctxt
);
752 gcc_jit_context_release (state
.ctxt
);
754 toyvm_compiled_function
*toyvm_result
=
755 (toyvm_compiled_function
*)calloc (1, sizeof (toyvm_compiled_function
));
758 fprintf (stderr
, "out of memory allocating toyvm_compiled_function\n");
759 gcc_jit_result_release (jit_result
);
763 toyvm_result
->cf_jit_result
= jit_result
;
764 toyvm_result
->cf_code
=
765 (toyvm_compiled_code
)gcc_jit_result_get_code (jit_result
,
775 #define CHECK_NON_NULL(PTR) \
779 pass ("%s: %s is non-null", test, #PTR); \
783 fail ("%s: %s is NULL", test, #PTR); \
788 #define CHECK_VALUE(ACTUAL, EXPECTED) \
790 if ((ACTUAL) == (EXPECTED)) \
792 pass ("%s: actual: %s == expected: %s", test, #ACTUAL, #EXPECTED); \
796 fail ("%s: actual: %s != expected: %s", test, #ACTUAL, #EXPECTED); \
797 fprintf (stderr, "incorrect value\n"); \
803 test_script (const char *scripts_dir
, const char *script_name
, int input
,
808 int interpreted_result
;
809 toyvm_compiled_function
*compiled_fn
;
810 toyvm_compiled_code code
;
813 snprintf (test
, sizeof (test
), "toyvm.c: %s", script_name
);
815 script_path
= (char *)malloc (strlen (scripts_dir
)
816 + strlen (script_name
) + 1);
817 CHECK_NON_NULL (script_path
);
818 sprintf (script_path
, "%s%s", scripts_dir
, script_name
);
820 fn
= toyvm_function_parse (script_path
, script_name
);
823 interpreted_result
= toyvm_function_interpret (fn
, input
, NULL
);
824 CHECK_VALUE (interpreted_result
, expected_result
);
826 compiled_fn
= toyvm_function_compile (fn
);
827 CHECK_NON_NULL (compiled_fn
);
829 code
= (toyvm_compiled_code
)compiled_fn
->cf_code
;
830 CHECK_NON_NULL (code
);
832 compiled_result
= code (input
);
833 CHECK_VALUE (compiled_result
, expected_result
);
835 gcc_jit_result_release (compiled_fn
->cf_jit_result
);
841 #define PATH_TO_SCRIPTS ("/jit/docs/examples/tut04-toyvm/")
849 snprintf (test
, sizeof (test
), "toyvm.c");
851 /* We need to locate the test scripts.
852 Rely on "srcdir" being set in the environment. */
854 srcdir
= getenv ("srcdir");
855 CHECK_NON_NULL (srcdir
);
857 scripts_dir
= (char *)malloc (strlen (srcdir
) + strlen(PATH_TO_SCRIPTS
)
859 CHECK_NON_NULL (scripts_dir
);
860 sprintf (scripts_dir
, "%s%s", srcdir
, PATH_TO_SCRIPTS
);
862 test_script (scripts_dir
, "factorial.toy", 10, 3628800);
863 test_script (scripts_dir
, "fibonacci.toy", 10, 55);
869 main (int argc
, char **argv
)
871 const char *filename
= NULL
;
872 toyvm_function
*fn
= NULL
;
874 /* If called with no args, assume we're being run by the test suite. */
884 "%s FILENAME INPUT: Parse and run a .toy file\n",
890 fn
= toyvm_function_parse (filename
, filename
);
895 toyvm_function_disassemble (fn
, stdout
);
897 printf ("interpreter result: %d\n",
898 toyvm_function_interpret (fn
, atoi (argv
[2]), NULL
));
900 /* JIT-compilation. */
901 toyvm_compiled_function
*compiled_fn
902 = toyvm_function_compile (fn
);
904 toyvm_compiled_code code
= compiled_fn
->cf_code
;
905 printf ("compiler result: %d\n",
906 code (atoi (argv
[2])));
908 gcc_jit_result_release (compiled_fn
->cf_jit_result
);