1 /* A simple stack-based virtual machine to demonstrate
3 Copyright (C) 2014-2016 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>
31 /* Functions are compiled to this function ptr type. */
32 typedef int (*toyvm_compiled_func
) (int);
35 /* Ops taking no operand. */
45 /* Ops taking an operand. */
50 #define FIRST_UNARY_OPCODE (PUSH_CONST)
52 const char * const opcode_names
[] = {
68 /* Which operation. */
69 enum opcode op_opcode
;
71 /* Some opcodes take an argument. */
74 /* The line number of the operation within the source file. */
84 add_op (enum opcode opcode
,
85 int operand
, int linenum
);
88 add_unary_op (enum opcode opcode
,
89 const char *rest_of_line
, int linenum
);
91 static toyvm_function
*
92 parse (const char *filename
, const char *name
);
95 disassemble_op (toyvm_op
*op
, int index
, FILE *out
);
98 disassemble (FILE *out
);
101 interpret (int arg
, FILE *trace
);
107 const char *fn_filename
;
109 toyvm_op fn_ops
[MAX_OPS
];
110 friend struct compilation_state
;
113 #define MAX_STACK_DEPTH (8)
120 void dump_stack (FILE *out
);
123 toyvm_function
*frm_function
;
125 int frm_stack
[MAX_STACK_DEPTH
];
128 friend int toyvm_function::interpret (int arg
, FILE *trace
);
133 toyvm_function::add_op (enum opcode opcode
,
134 int operand
, int linenum
)
137 assert (fn_num_ops
< MAX_OPS
);
138 op
= &fn_ops
[fn_num_ops
++];
139 op
->op_opcode
= opcode
;
140 op
->op_operand
= operand
;
141 op
->op_linenum
= linenum
;
145 toyvm_function::add_unary_op (enum opcode opcode
,
146 const char *rest_of_line
, int linenum
)
148 int operand
= atoi (rest_of_line
);
149 add_op (opcode
, operand
, linenum
);
153 get_function_name (const char *filename
)
155 /* Skip any path separators. */
156 const char *pathsep
= strrchr (filename
, '/');
158 filename
= pathsep
+ 1;
160 /* Copy filename to funcname. */
161 char *funcname
= (char *)malloc (strlen (filename
) + 1);
163 strcpy (funcname
, filename
);
165 /* Convert "." to NIL terminator. */
166 *(strchr (funcname
, '.')) = '\0';
172 toyvm_function::parse (const char *filename
, const char *name
)
175 toyvm_function
*fn
= NULL
;
184 f
= fopen (filename
, "r");
188 "cannot open file %s: %s\n",
189 filename
, strerror (errno
));
193 fn
= (toyvm_function
*)calloc (1, sizeof (toyvm_function
));
196 fprintf (stderr
, "out of memory allocating toyvm_function\n");
199 fn
->fn_filename
= filename
;
201 /* Read the lines of the file. */
202 while ((linelen
= getline (&line
, &bufsize
, f
)) != -1)
204 /* Note that this is a terrible parser, but it avoids the need to
205 bring in lex/yacc as a dependency. */
209 fprintf (stdout
, "%3d: %s", linenum
, line
);
211 /* Lines beginning with # are comments. */
215 /* Skip blank lines. */
219 #define LINE_MATCHES(OPCODE) (0 == strncmp ((OPCODE), line, strlen (OPCODE)))
220 if (LINE_MATCHES ("DUP\n"))
221 fn
->add_op (DUP
, 0, linenum
);
222 else if (LINE_MATCHES ("ROT\n"))
223 fn
->add_op (ROT
, 0, linenum
);
224 else if (LINE_MATCHES ("BINARY_ADD\n"))
225 fn
->add_op (BINARY_ADD
, 0, linenum
);
226 else if (LINE_MATCHES ("BINARY_SUBTRACT\n"))
227 fn
->add_op (BINARY_SUBTRACT
, 0, linenum
);
228 else if (LINE_MATCHES ("BINARY_MULT\n"))
229 fn
->add_op (BINARY_MULT
, 0, linenum
);
230 else if (LINE_MATCHES ("BINARY_COMPARE_LT\n"))
231 fn
->add_op (BINARY_COMPARE_LT
, 0, linenum
);
232 else if (LINE_MATCHES ("RECURSE\n"))
233 fn
->add_op (RECURSE
, 0, linenum
);
234 else if (LINE_MATCHES ("RETURN\n"))
235 fn
->add_op (RETURN
, 0, linenum
);
236 else if (LINE_MATCHES ("PUSH_CONST "))
237 fn
->add_unary_op (PUSH_CONST
,
238 line
+ strlen ("PUSH_CONST "), linenum
);
239 else if (LINE_MATCHES ("JUMP_ABS_IF_TRUE "))
240 fn
->add_unary_op (JUMP_ABS_IF_TRUE
,
241 line
+ strlen("JUMP_ABS_IF_TRUE "), linenum
);
244 fprintf (stderr
, "%s:%d: parse error\n", filename
, linenum
);
265 toyvm_function::disassemble_op (toyvm_op
*op
, int index
, FILE *out
)
267 fprintf (out
, "%s:%d: index %d: %s",
268 fn_filename
, op
->op_linenum
, index
,
269 opcode_names
[op
->op_opcode
]);
270 if (op
->op_opcode
>= FIRST_UNARY_OPCODE
)
271 fprintf (out
, " %d", op
->op_operand
);
276 toyvm_function::disassemble (FILE *out
)
279 for (i
= 0; i
< fn_num_ops
; i
++)
281 toyvm_op
*op
= &fn_ops
[i
];
282 disassemble_op (op
, i
, out
);
287 toyvm_frame::push (int arg
)
289 assert (frm_cur_depth
< MAX_STACK_DEPTH
);
290 frm_stack
[frm_cur_depth
++] = arg
;
296 assert (frm_cur_depth
> 0);
297 return frm_stack
[--frm_cur_depth
];
301 toyvm_frame::dump_stack (FILE *out
)
304 fprintf (out
, "stack:");
305 for (i
= 0; i
< frm_cur_depth
; i
++)
307 fprintf (out
, " %d", frm_stack
[i
]);
312 /* Execute the given function. */
315 toyvm_function::interpret (int arg
, FILE *trace
)
318 #define PUSH(ARG) (frame.push (ARG))
319 #define POP(ARG) (frame.pop ())
321 frame
.frm_function
= this;
323 frame
.frm_cur_depth
= 0;
331 assert (frame
.frm_pc
< fn_num_ops
);
332 op
= &fn_ops
[frame
.frm_pc
++];
336 frame
.dump_stack (trace
);
337 disassemble_op (op
, frame
.frm_pc
, trace
);
340 switch (op
->op_opcode
)
342 /* Ops taking no operand. */
362 case BINARY_SUBTRACT
:
374 case BINARY_COMPARE_LT
:
382 x
= interpret (x
, trace
);
389 /* Ops taking an operand. */
391 PUSH (op
->op_operand
);
394 case JUMP_ABS_IF_TRUE
:
397 frame
.frm_pc
= op
->op_operand
;
401 assert (0); /* unknown opcode */
403 } /* end of switch on opcode */
404 } /* end of while loop */
410 /* JIT compilation. */
412 class compilation_state
415 compilation_state (toyvm_function
&toyvmfn
) :
419 void create_context ();
420 void create_types ();
421 void create_locations ();
422 void create_function (const char *funcname
);
423 gcc_jit_result
*compile ();
427 add_push (gccjit::block block
,
428 gccjit::rvalue rvalue
,
429 gccjit::location loc
);
432 add_pop (gccjit::block block
,
433 gccjit::lvalue lvalue
,
434 gccjit::location loc
);
440 toyvm_function
&toyvmfn
;
442 gccjit::context ctxt
;
444 gccjit::type int_type
;
445 gccjit::type bool_type
;
446 gccjit::type stack_type
; /* int[MAX_STACK_DEPTH] */
448 gccjit::rvalue const_one
;
451 gccjit::param param_arg
;
452 gccjit::lvalue stack
;
453 gccjit::lvalue stack_depth
;
457 gccjit::location op_locs
[MAX_OPS
];
458 gccjit::block initial_block
;
459 gccjit::block op_blocks
[MAX_OPS
];
463 /* The main compilation hook. */
466 toyvm_function::compile ()
468 compilation_state
state (*this);
471 funcname
= get_function_name (fn_filename
);
473 state
.create_context ();
474 state
.create_types ();
475 state
.create_locations ();
476 state
.create_function (funcname
);
478 /* We've now finished populating the context. Compile it. */
479 gcc_jit_result
*result
= state
.compile ();
481 return (toyvm_compiled_func
)gcc_jit_result_get_code (result
, funcname
);
482 /* (this leaks "result" and "funcname") */
485 /* Stack manipulation. */
488 compilation_state::add_push (gccjit::block block
,
489 gccjit::rvalue rvalue
,
490 gccjit::location loc
)
492 /* stack[stack_depth] = RVALUE */
493 block
.add_assignment (
494 /* stack[stack_depth] */
495 ctxt
.new_array_access (
502 /* "stack_depth++;". */
503 block
.add_assignment_op (
505 GCC_JIT_BINARY_OP_PLUS
,
511 compilation_state::add_pop (gccjit::block block
,
512 gccjit::lvalue lvalue
,
513 gccjit::location loc
)
515 /* "--stack_depth;". */
516 block
.add_assignment_op (
518 GCC_JIT_BINARY_OP_MINUS
,
522 /* "LVALUE = stack[stack_depth];". */
523 block
.add_assignment (
525 /* stack[stack_depth] */
526 ctxt
.new_array_access (stack
,
532 /* Create the context. */
535 compilation_state::create_context ()
537 ctxt
= gccjit::context::acquire ();
539 ctxt
.set_bool_option (GCC_JIT_BOOL_OPTION_DUMP_INITIAL_GIMPLE
,
541 ctxt
.set_bool_option (GCC_JIT_BOOL_OPTION_DUMP_GENERATED_CODE
,
543 ctxt
.set_int_option (GCC_JIT_INT_OPTION_OPTIMIZATION_LEVEL
,
545 ctxt
.set_bool_option (GCC_JIT_BOOL_OPTION_KEEP_INTERMEDIATES
,
547 ctxt
.set_bool_option (GCC_JIT_BOOL_OPTION_DUMP_EVERYTHING
,
549 ctxt
.set_bool_option (GCC_JIT_BOOL_OPTION_DEBUGINFO
,
556 compilation_state::create_types ()
559 int_type
= ctxt
.get_type (GCC_JIT_TYPE_INT
);
560 bool_type
= ctxt
.get_type (GCC_JIT_TYPE_BOOL
);
561 stack_type
= ctxt
.new_array_type (int_type
, MAX_STACK_DEPTH
);
563 /* The constant value 1. */
564 const_one
= ctxt
.one (int_type
);
568 /* Create locations. */
571 compilation_state::create_locations ()
573 for (int pc
= 0; pc
< toyvmfn
.fn_num_ops
; pc
++)
575 toyvm_op
*op
= &toyvmfn
.fn_ops
[pc
];
577 op_locs
[pc
] = ctxt
.new_location (toyvmfn
.fn_filename
,
583 /* Creating the function. */
586 compilation_state::create_function (const char *funcname
)
588 std::vector
<gccjit::param
> params
;
589 param_arg
= ctxt
.new_param (int_type
, "arg", op_locs
[0]);
590 params
.push_back (param_arg
);
591 fn
= ctxt
.new_function (GCC_JIT_FUNCTION_EXPORTED
,
597 /* Create stack lvalues. */
598 stack
= fn
.new_local (stack_type
, "stack");
599 stack_depth
= fn
.new_local (int_type
, "stack_depth");
600 x
= fn
.new_local (int_type
, "x");
601 y
= fn
.new_local (int_type
, "y");
603 /* 1st pass: create blocks, one per opcode. */
605 /* We need an entry block to do one-time initialization, so create that
607 initial_block
= fn
.new_block ("initial");
609 /* Create a block per operation. */
610 for (int pc
= 0; pc
< toyvmfn
.fn_num_ops
; pc
++)
613 sprintf (buf
, "instr%i", pc
);
614 op_blocks
[pc
] = fn
.new_block (buf
);
617 /* Populate the initial block. */
619 /* "stack_depth = 0;". */
620 initial_block
.add_assignment (stack_depth
,
621 ctxt
.zero (int_type
),
625 add_push (initial_block
,
629 /* ...and jump to insn 0. */
630 initial_block
.end_with_jump (op_blocks
[0],
633 /* 2nd pass: fill in instructions. */
634 for (int pc
= 0; pc
< toyvmfn
.fn_num_ops
; pc
++)
636 gccjit::location loc
= op_locs
[pc
];
638 gccjit::block block
= op_blocks
[pc
];
639 gccjit::block next_block
= (pc
< toyvmfn
.fn_num_ops
644 op
= &toyvmfn
.fn_ops
[pc
];
648 #define X_EQUALS_POP()\
649 add_pop (block, x, loc)
650 #define Y_EQUALS_POP()\
651 add_pop (block, y, loc)
652 #define PUSH_RVALUE(RVALUE)\
653 add_push (block, (RVALUE), loc)
659 block
.add_comment (opcode_names
[op
->op_opcode
], loc
);
661 /* Handle the individual opcodes. */
663 switch (op
->op_opcode
)
683 GCC_JIT_BINARY_OP_PLUS
,
689 case BINARY_SUBTRACT
:
694 GCC_JIT_BINARY_OP_MINUS
,
705 GCC_JIT_BINARY_OP_MULT
,
711 case BINARY_COMPARE_LT
:
715 /* cast of bool to int */
717 /* (x < y) as a bool */
718 ctxt
.new_comparison (
719 GCC_JIT_COMPARISON_LT
,
739 block
.end_with_return (x
, loc
);
742 /* Ops taking an operand. */
745 ctxt
.new_rvalue (int_type
, op
->op_operand
));
748 case JUMP_ABS_IF_TRUE
:
750 block
.end_with_conditional (
752 ctxt
.new_cast (x
, bool_type
, loc
),
753 op_blocks
[op
->op_operand
], /* on_true */
754 next_block
, /* on_false */
760 } /* end of switch on opcode */
762 /* Go to the next block. */
763 if (op
->op_opcode
!= JUMP_ABS_IF_TRUE
764 && op
->op_opcode
!= RETURN
)
765 block
.end_with_jump (next_block
, loc
);
767 } /* end of loop on PC locations. */
771 compilation_state::compile ()
773 return ctxt
.compile ();
778 #define CHECK_NON_NULL(PTR) \
782 pass ("%s: %s is non-null", test, #PTR); \
786 fail ("%s: %s is NULL", test, #PTR); \
791 #define CHECK_VALUE(ACTUAL, EXPECTED) \
793 if ((ACTUAL) == (EXPECTED)) \
795 pass ("%s: actual: %s == expected: %s", test, #ACTUAL, #EXPECTED); \
799 fail ("%s: actual: %s != expected: %s", test, #ACTUAL, #EXPECTED); \
800 fprintf (stderr, "incorrect value\n"); \
806 test_script (const char *scripts_dir
, const char *script_name
, int input
,
811 int interpreted_result
;
812 toyvm_compiled_func code
;
815 snprintf (test
, sizeof (test
), "toyvm.cc: %s", script_name
);
817 script_path
= (char *)malloc (strlen (scripts_dir
)
818 + strlen (script_name
) + 1);
819 CHECK_NON_NULL (script_path
);
820 sprintf (script_path
, "%s%s", scripts_dir
, script_name
);
822 fn
= toyvm_function::parse (script_path
, script_name
);
825 interpreted_result
= fn
->interpret (input
, NULL
);
826 CHECK_VALUE (interpreted_result
, expected_result
);
828 code
= fn
->compile ();
829 CHECK_NON_NULL (code
);
831 compiled_result
= code (input
);
832 CHECK_VALUE (compiled_result
, expected_result
);
837 #define PATH_TO_SCRIPTS ("/jit/docs/examples/tut04-toyvm/")
845 snprintf (test
, sizeof (test
), "toyvm.cc");
847 /* We need to locate the test scripts.
848 Rely on "srcdir" being set in the environment. */
850 srcdir
= getenv ("srcdir");
851 CHECK_NON_NULL (srcdir
);
853 scripts_dir
= (char *)malloc (strlen (srcdir
) + strlen(PATH_TO_SCRIPTS
)
855 CHECK_NON_NULL (scripts_dir
);
856 sprintf (scripts_dir
, "%s%s", srcdir
, PATH_TO_SCRIPTS
);
858 test_script (scripts_dir
, "factorial.toy", 10, 3628800);
859 test_script (scripts_dir
, "fibonacci.toy", 10, 55);
865 main (int argc
, char **argv
)
867 const char *filename
= NULL
;
868 toyvm_function
*fn
= NULL
;
870 /* If called with no args, assume we're being run by the test suite. */
880 "%s FILENAME INPUT: Parse and run a .toy file\n",
886 fn
= toyvm_function::parse (filename
, filename
);
891 fn
->disassemble (stdout
);
893 printf ("interpreter result: %d\n",
894 fn
->interpret (atoi (argv
[2]), NULL
));
896 /* JIT-compilation. */
897 toyvm_compiled_func code
= fn
->compile ();
898 printf ("compiler result: %d\n",
899 code (atoi (argv
[2])));