| .. Copyright (C) 2014-2026 Free Software Foundation, Inc. | |
| Originally contributed by David Malcolm <dmalcolm@redhat.com> | |
| This is free software: you can redistribute it and/or modify it | |
| under the terms of the GNU General Public License as published by | |
| the Free Software Foundation, either version 3 of the License, or | |
| (at your option) any later version. | |
| This program is distributed in the hope that it will be useful, but | |
| WITHOUT ANY WARRANTY; without even the implied warranty of | |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| General Public License for more details. | |
| You should have received a copy of the GNU General Public License | |
| along with this program. If not, see | |
| <https://www.gnu.org/licenses/>. | |
| Tutorial part 4: Adding JIT-compilation to a toy interpreter | |
| ------------------------------------------------------------ | |
| In this example we construct a "toy" interpreter, and add JIT-compilation | |
| to it. | |
| Our toy interpreter | |
| ******************* | |
| It's a stack-based interpreter, and is intended as a (very simple) example | |
| of the kind of bytecode interpreter seen in dynamic languages such as | |
| Python, Ruby etc. | |
| For the sake of simplicity, our toy virtual machine is very limited: | |
| * The only data type is `int` | |
| * It can only work on one function at a time (so that the only | |
| function call that can be made is to recurse). | |
| * Functions can only take one parameter. | |
| * Functions have a stack of `int` values. | |
| * We'll implement function call within the interpreter by calling a | |
| function in our implementation, rather than implementing our own | |
| frame stack. | |
| * The parser is only good enough to get the examples to work. | |
| Naturally, a real interpreter would be much more complicated that this. | |
| The following operations are supported: | |
| .. list-table:: | |
| :header-rows: 1 | |
| :widths: 35 50 25 25 | |
| * - Operation | |
| - Meaning | |
| - Old Stack | |
| - New Stack | |
| * - DUP | |
| - Duplicate top of stack. | |
| - ``[..., x]`` | |
| - ``[..., x, x]`` | |
| * - ROT | |
| - Swap top two elements of stack. | |
| - ``[..., x, y]`` | |
| - ``[..., y, x]`` | |
| * - BINARY_ADD | |
| - Add the top two elements on the stack. | |
| - ``[..., x, y]`` | |
| - ``[..., (x+y)]`` | |
| * - BINARY_SUBTRACT | |
| - Likewise, but subtract. | |
| - ``[..., x, y]`` | |
| - ``[..., (x-y)]`` | |
| * - BINARY_MULT | |
| - Likewise, but multiply. | |
| - ``[..., x, y]`` | |
| - ``[..., (x*y)]`` | |
| * - BINARY_COMPARE_LT | |
| - Compare the top two elements on the stack and push a nonzero/zero if (x<y). | |
| - ``[..., x, y]`` | |
| - ``[..., (x<y)]`` | |
| * - RECURSE | |
| - Recurse, passing the top of the stack, and popping the result. | |
| - ``[..., x]`` | |
| - ``[..., fn(x)]`` | |
| * - RETURN | |
| - Return the top of the stack. | |
| - ``[x]`` | |
| - ``[]`` | |
| * - PUSH_CONST `arg` | |
| - Push an int const. | |
| - ``[...]`` | |
| - ``[..., arg]`` | |
| * - JUMP_ABS_IF_TRUE `arg` | |
| - Pop; if top of stack was nonzero, jump to ``arg``. | |
| - ``[..., x]`` | |
| - ``[...]`` | |
| Programs can be interpreted, disassembled, and compiled to machine code. | |
| The interpreter reads ``.toy`` scripts. Here's what a simple recursive | |
| factorial program looks like, the script ``factorial.toy``. | |
| The parser ignores lines beginning with a `#`. | |
| .. literalinclude:: ../examples/tut04-toyvm/factorial.toy | |
| :lines: 1- | |
| :language: c | |
| The interpreter is a simple infinite loop with a big ``switch`` statement | |
| based on what the next opcode is: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Execute the given function. */ | |
| :end-before: /* JIT compilation. */ | |
| :language: c | |
| Compiling to machine code | |
| ************************* | |
| We want to generate machine code that can be cast to this type and | |
| then directly executed in-process: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Functions are compiled to this function ptr type. */ | |
| :end-before: enum opcode | |
| :language: c | |
| The lifetime of the code is tied to that of a :c:expr:`gcc_jit_result *`. | |
| We'll handle this by bundling them up in a structure, so that we can | |
| clean them up together by calling :c:func:`gcc_jit_result_release`: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* A struct to hold the compilation results. */ | |
| :end-before: /* The main compilation hook. */ | |
| :language: c | |
| Our compiler isn't very sophisticated; it takes the implementation of | |
| each opcode above, and maps it directly to the operations supported by | |
| the libgccjit API. | |
| How should we handle the stack? In theory we could calculate what the | |
| stack depth will be at each opcode, and optimize away the stack | |
| manipulation "by hand". We'll see below that libgccjit is able to do | |
| this for us, so we'll implement stack manipulation | |
| in a direct way, by creating a ``stack`` array and ``stack_depth`` | |
| variables, local within the generated function, equivalent to this C code: | |
| .. code-block:: c | |
| int stack_depth; | |
| int stack[MAX_STACK_DEPTH]; | |
| We'll also have local variables ``x`` and ``y`` for use when implementing | |
| the opcodes, equivalent to this: | |
| .. code-block:: c | |
| int x; | |
| int y; | |
| This means our compiler has the following state: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* JIT compilation. */ | |
| :end-before: /* Stack manipulation. */ | |
| :language: c | |
| Setting things up | |
| ***************** | |
| First we create our types: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Create types. */ | |
| :end-before: /* The constant value 1. */ | |
| :language: c | |
| along with extracting a useful `int` constant: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* The constant value 1. */ | |
| :end-before: /* Create locations. */ | |
| :language: c | |
| We'll implement push and pop in terms of the ``stack`` array and | |
| ``stack_depth``. Here are helper functions for adding statements to | |
| a block, implementing pushing and popping values: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Stack manipulation. */ | |
| :end-before: /* A struct to hold the compilation results. */ | |
| :language: c | |
| We will support single-stepping through the generated code in the | |
| debugger, so we need to create :c:type:`gcc_jit_location` instances, one | |
| per operation in the source code. These will reference the lines of | |
| e.g. ``factorial.toy``. | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Create locations. */ | |
| :end-before: /* Creating the function. */ | |
| :language: c | |
| Let's create the function itself. As usual, we create its parameter | |
| first, then use the parameter to create the function: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Creating the function. */ | |
| :end-before: /* Create stack lvalues. */ | |
| :language: c | |
| We create the locals within the function. | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Create stack lvalues. */ | |
| :end-before: /* 1st pass: create blocks, one per opcode. | |
| :language: c | |
| Populating the function | |
| *********************** | |
| There's some one-time initialization, and the API treats the first block | |
| you create as the entrypoint of the function, so we need to create that | |
| block first: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: first. */ | |
| :end-before: /* Create a block per operation. */ | |
| :language: c | |
| We can now create blocks for each of the operations. Most of these will | |
| be consolidated into larger blocks when the optimizer runs. | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Create a block per operation. */ | |
| :end-before: /* Populate the initial block. */ | |
| :language: c | |
| Now that we have a block it can jump to when it's done, we can populate | |
| the initial block: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Populate the initial block. */ | |
| :end-before: /* 2nd pass: fill in instructions. */ | |
| :language: c | |
| We can now populate the blocks for the individual operations. We loop | |
| through them, adding instructions to their blocks: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* 2nd pass: fill in instructions. */ | |
| :end-before: /* Helper macros. */ | |
| :language: c | |
| We're going to have another big ``switch`` statement for implementing | |
| the opcodes, this time for compiling them, rather than interpreting | |
| them. It's helpful to have macros for implementing push and pop, so that | |
| we can make the ``switch`` statement that's coming up look as much as | |
| possible like the one above within the interpreter: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Helper macros. */ | |
| :end-before: gcc_jit_block_add_comment | |
| :language: c | |
| .. note:: | |
| A particularly clever implementation would have an *identical* | |
| ``switch`` statement shared by the interpreter and the compiler, with | |
| some preprocessor "magic". We're not doing that here, for the sake | |
| of simplicity. | |
| When I first implemented this compiler, I accidentally missed an edit | |
| when copying and pasting the ``Y_EQUALS_POP`` macro, so that popping the | |
| stack into ``y`` instead erroneously assigned it to ``x``, leaving ``y`` | |
| uninitialized. | |
| To track this kind of thing down, we can use | |
| :c:func:`gcc_jit_block_add_comment` to add descriptive comments | |
| to the internal representation. This is invaluable when looking through | |
| the generated IR for, say ``factorial``: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: PUSH_RVALUE (gcc_jit_lvalue_as_rvalue (state.y)) | |
| :end-before: /* Handle the individual opcodes. */ | |
| :language: c | |
| We can now write the big ``switch`` statement that implements the | |
| individual opcodes, populating the relevant block with statements: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Handle the individual opcodes. */ | |
| :end-before: /* Go to the next block. */ | |
| :language: c | |
| Every block must be terminated, via a call to one of the | |
| ``gcc_jit_block_end_with_`` entrypoints. This has been done for two | |
| of the opcodes, but we need to do it for the other ones, by jumping | |
| to the next block. | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* Go to the next block. */ | |
| :end-before: /* end of loop on PC locations. */ | |
| :language: c | |
| This is analogous to simply incrementing the program counter. | |
| Verifying the control flow graph | |
| ******************************** | |
| Having finished looping over the blocks, the context is complete. | |
| As before, we can verify that the control flow and statements are sane by | |
| using :c:func:`gcc_jit_function_dump_to_dot`: | |
| .. code-block:: c | |
| gcc_jit_function_dump_to_dot (state.fn, "/tmp/factorial.dot"); | |
| and viewing the result. Note how the label names, comments, and | |
| variable names show up in the dump, to make it easier to spot | |
| errors in our compiler. | |
| .. figure:: factorial.png | |
| :alt: image of a control flow graph | |
| Compiling the context | |
| ********************* | |
| Having finished looping over the blocks and populating them with | |
| statements, the context is complete. | |
| We can now compile it, and extract machine code from the result: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* We've now finished populating the context. Compile it. */ | |
| :end-before: /* (this leaks "jit_result" and "funcname") */ | |
| :language: c | |
| We can now run the result: | |
| .. literalinclude:: ../examples/tut04-toyvm/toyvm.c | |
| :start-after: /* JIT-compilation. */ | |
| :end-before: return 0; | |
| :language: c | |
| Single-stepping through the generated code | |
| ****************************************** | |
| It's possible to debug the generated code. To do this we need to both: | |
| * Set up source code locations for our statements, so that we can | |
| meaningfully step through the code. We did this above by | |
| calling :c:func:`gcc_jit_context_new_location` and using the | |
| results. | |
| * Enable the generation of debugging information, by setting | |
| :c:macro:`GCC_JIT_BOOL_OPTION_DEBUGINFO` on the | |
| :c:type:`gcc_jit_context` via | |
| :c:func:`gcc_jit_context_set_bool_option`: | |
| .. code-block:: c | |
| gcc_jit_context_set_bool_option ( | |
| ctxt, | |
| GCC_JIT_BOOL_OPTION_DEBUGINFO, | |
| 1); | |
| Having done this, we can put a breakpoint on the generated function: | |
| .. code-block:: console | |
| $ gdb --args ./toyvm factorial.toy 10 | |
| (gdb) break factorial | |
| Function "factorial" not defined. | |
| Make breakpoint pending on future shared library load? (y or [n]) y | |
| Breakpoint 1 (factorial) pending. | |
| (gdb) run | |
| Breakpoint 1, factorial (arg=10) at factorial.toy:14 | |
| 14 DUP | |
| We've set up location information, which references ``factorial.toy``. | |
| This allows us to use e.g. ``list`` to see where we are in the script: | |
| .. code-block:: console | |
| (gdb) list | |
| 9 | |
| 10 # Initial state: | |
| 11 # stack: [arg] | |
| 12 | |
| 13 # 0: | |
| 14 DUP | |
| 15 # stack: [arg, arg] | |
| 16 | |
| 17 # 1: | |
| 18 PUSH_CONST 2 | |
| and to step through the function, examining the data: | |
| .. code-block:: console | |
| (gdb) n | |
| 18 PUSH_CONST 2 | |
| (gdb) n | |
| 22 BINARY_COMPARE_LT | |
| (gdb) print stack | |
| $5 = {10, 10, 2, 0, -7152, 32767, 0, 0} | |
| (gdb) print stack_depth | |
| $6 = 3 | |
| You'll see that the parts of the ``stack`` array that haven't been | |
| touched yet are uninitialized. | |
| .. note:: | |
| Turning on optimizations may lead to unpredictable results when | |
| stepping through the generated code: the execution may appear to | |
| "jump around" the source code. This is analogous to turning up the | |
| optimization level in a regular compiler. | |
| Examining the generated code | |
| **************************** | |
| How good is the optimized code? | |
| We can turn up optimizations, by calling | |
| :c:func:`gcc_jit_context_set_int_option` with | |
| :c:macro:`GCC_JIT_INT_OPTION_OPTIMIZATION_LEVEL`: | |
| .. code-block:: c | |
| gcc_jit_context_set_int_option ( | |
| ctxt, | |
| GCC_JIT_INT_OPTION_OPTIMIZATION_LEVEL, | |
| 3); | |
| One of GCC's internal representations is called "gimple". A dump of the | |
| initial gimple representation of the code can be seen by setting: | |
| .. code-block:: c | |
| gcc_jit_context_set_bool_option (ctxt, | |
| GCC_JIT_BOOL_OPTION_DUMP_INITIAL_GIMPLE, | |
| 1); | |
| With optimization on and source locations displayed, this gives: | |
| .. We'll use "c" for gimple dumps | |
| .. code-block:: c | |
| factorial (signed int arg) | |
| { | |
| <unnamed type> D.80; | |
| signed int D.81; | |
| signed int D.82; | |
| signed int D.83; | |
| signed int D.84; | |
| signed int D.85; | |
| signed int y; | |
| signed int x; | |
| signed int stack_depth; | |
| signed int stack[8]; | |
| try | |
| { | |
| initial: | |
| stack_depth = 0; | |
| stack[stack_depth] = arg; | |
| stack_depth = stack_depth + 1; | |
| goto instr0; | |
| instr0: | |
| /* DUP */: | |
| stack_depth = stack_depth + -1; | |
| x = stack[stack_depth]; | |
| stack[stack_depth] = x; | |
| stack_depth = stack_depth + 1; | |
| stack[stack_depth] = x; | |
| stack_depth = stack_depth + 1; | |
| goto instr1; | |
| instr1: | |
| /* PUSH_CONST */: | |
| stack[stack_depth] = 2; | |
| stack_depth = stack_depth + 1; | |
| goto instr2; | |
| /* etc */ | |
| You can see the generated machine code in assembly form via: | |
| .. code-block:: c | |
| gcc_jit_context_set_bool_option ( | |
| ctxt, | |
| GCC_JIT_BOOL_OPTION_DUMP_GENERATED_CODE, | |
| 1); | |
| result = gcc_jit_context_compile (ctxt); | |
| which shows that (on this x86_64 box) the compiler has unrolled the loop | |
| and is using MMX instructions to perform several multiplications | |
| simultaneously: | |
| .. code-block:: gas | |
| .file "fake.c" | |
| .text | |
| .Ltext0: | |
| .p2align 4,,15 | |
| .globl factorial | |
| .type factorial, @function | |
| factorial: | |
| .LFB0: | |
| .file 1 "factorial.toy" | |
| .loc 1 14 0 | |
| .cfi_startproc | |
| .LVL0: | |
| .L2: | |
| .loc 1 26 0 | |
| cmpl $1, %edi | |
| jle .L13 | |
| leal -1(%rdi), %edx | |
| movl %edx, %ecx | |
| shrl $2, %ecx | |
| leal 0(,%rcx,4), %esi | |
| testl %esi, %esi | |
| je .L14 | |
| cmpl $9, %edx | |
| jbe .L14 | |
| leal -2(%rdi), %eax | |
| movl %eax, -16(%rsp) | |
| leal -3(%rdi), %eax | |
| movd -16(%rsp), %xmm0 | |
| movl %edi, -16(%rsp) | |
| movl %eax, -12(%rsp) | |
| movd -16(%rsp), %xmm1 | |
| xorl %eax, %eax | |
| movl %edx, -16(%rsp) | |
| movd -12(%rsp), %xmm4 | |
| movd -16(%rsp), %xmm6 | |
| punpckldq %xmm4, %xmm0 | |
| movdqa .LC1(%rip), %xmm4 | |
| punpckldq %xmm6, %xmm1 | |
| punpcklqdq %xmm0, %xmm1 | |
| movdqa .LC0(%rip), %xmm0 | |
| jmp .L5 | |
| # etc - edited for brevity | |
| This is clearly overkill for a function that will likely overflow the | |
| ``int`` type before the vectorization is worthwhile - but then again, this | |
| is a toy example. | |
| Turning down the optimization level to 2: | |
| .. code-block:: c | |
| gcc_jit_context_set_int_option ( | |
| ctxt, | |
| GCC_JIT_INT_OPTION_OPTIMIZATION_LEVEL, | |
| 3); | |
| yields this code, which is simple enough to quote in its entirety: | |
| .. code-block:: gas | |
| .file "fake.c" | |
| .text | |
| .p2align 4,,15 | |
| .globl factorial | |
| .type factorial, @function | |
| factorial: | |
| .LFB0: | |
| .cfi_startproc | |
| .L2: | |
| cmpl $1, %edi | |
| jle .L8 | |
| movl $1, %edx | |
| jmp .L4 | |
| .p2align 4,,10 | |
| .p2align 3 | |
| .L6: | |
| movl %eax, %edi | |
| .L4: | |
| .L5: | |
| leal -1(%rdi), %eax | |
| imull %edi, %edx | |
| cmpl $1, %eax | |
| jne .L6 | |
| .L3: | |
| .L7: | |
| imull %edx, %eax | |
| ret | |
| .L8: | |
| movl %edi, %eax | |
| movl $1, %edx | |
| jmp .L7 | |
| .cfi_endproc | |
| .LFE0: | |
| .size factorial, .-factorial | |
| .ident "GCC: (GNU) 4.9.0 20131023 (Red Hat 0.2)" | |
| .section .note.GNU-stack,"",@progbits | |
| Note that the stack pushing and popping have been eliminated, as has the | |
| recursive call (in favor of an iteration). | |
| Putting it all together | |
| *********************** | |
| The complete example can be seen in the source tree at | |
| ``gcc/jit/docs/examples/tut04-toyvm/toyvm.c`` | |
| along with a Makefile and a couple of sample .toy scripts: | |
| .. code-block:: console | |
| $ ls -al | |
| drwxrwxr-x. 2 david david 4096 Sep 19 17:46 . | |
| drwxrwxr-x. 3 david david 4096 Sep 19 15:26 .. | |
| -rw-rw-r--. 1 david david 615 Sep 19 12:43 factorial.toy | |
| -rw-rw-r--. 1 david david 834 Sep 19 13:08 fibonacci.toy | |
| -rw-rw-r--. 1 david david 238 Sep 19 14:22 Makefile | |
| -rw-rw-r--. 1 david david 16457 Sep 19 17:07 toyvm.c | |
| $ make toyvm | |
| g++ -Wall -g -o toyvm toyvm.c -lgccjit | |
| $ ./toyvm factorial.toy 10 | |
| interpreter result: 3628800 | |
| compiler result: 3628800 | |
| $ ./toyvm fibonacci.toy 10 | |
| interpreter result: 55 | |
| compiler result: 55 | |
| Behind the curtain: How does our code get optimized? | |
| **************************************************** | |
| Our example is done, but you may be wondering about exactly how the | |
| compiler turned what we gave it into the machine code seen above. | |
| We can examine what the compiler is doing in detail by setting: | |
| .. code-block:: c | |
| gcc_jit_context_set_bool_option (state.ctxt, | |
| GCC_JIT_BOOL_OPTION_DUMP_EVERYTHING, | |
| 1); | |
| gcc_jit_context_set_bool_option (state.ctxt, | |
| GCC_JIT_BOOL_OPTION_KEEP_INTERMEDIATES, | |
| 1); | |
| This will dump detailed information about the compiler's state to a | |
| directory under ``/tmp``, and keep it from being cleaned up. | |
| The precise names and their formats of these files is subject to change. | |
| Higher optimization levels lead to more files. | |
| Here's what I saw (edited for brevity; there were almost 200 files): | |
| .. code-block:: console | |
| intermediate files written to /tmp/libgccjit-KPQbGw | |
| $ ls /tmp/libgccjit-KPQbGw/ | |
| fake.c.000i.cgraph | |
| fake.c.000i.type-inheritance | |
| fake.c.004t.gimple | |
| fake.c.007t.omplower | |
| fake.c.008t.lower | |
| fake.c.011t.eh | |
| fake.c.012t.cfg | |
| fake.c.014i.visibility | |
| fake.c.015i.early_local_cleanups | |
| fake.c.016t.ssa | |
| # etc | |
| The gimple code is converted into Static Single Assignment form, | |
| with annotations for use when generating the debuginfo: | |
| .. code-block:: console | |
| $ less /tmp/libgccjit-KPQbGw/fake.c.016t.ssa | |
| .. code-block:: c | |
| ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0) | |
| factorial (signed int arg) | |
| { | |
| signed int stack[8]; | |
| signed int stack_depth; | |
| signed int x; | |
| signed int y; | |
| <unnamed type> _20; | |
| signed int _21; | |
| signed int _38; | |
| signed int _44; | |
| signed int _51; | |
| signed int _56; | |
| initial: | |
| stack_depth_3 = 0; | |
| # DEBUG stack_depth => stack_depth_3 | |
| stack[stack_depth_3] = arg_5(D); | |
| stack_depth_7 = stack_depth_3 + 1; | |
| # DEBUG stack_depth => stack_depth_7 | |
| # DEBUG instr0 => NULL | |
| # DEBUG /* DUP */ => NULL | |
| stack_depth_8 = stack_depth_7 + -1; | |
| # DEBUG stack_depth => stack_depth_8 | |
| x_9 = stack[stack_depth_8]; | |
| # DEBUG x => x_9 | |
| stack[stack_depth_8] = x_9; | |
| stack_depth_11 = stack_depth_8 + 1; | |
| # DEBUG stack_depth => stack_depth_11 | |
| stack[stack_depth_11] = x_9; | |
| stack_depth_13 = stack_depth_11 + 1; | |
| # DEBUG stack_depth => stack_depth_13 | |
| # DEBUG instr1 => NULL | |
| # DEBUG /* PUSH_CONST */ => NULL | |
| stack[stack_depth_13] = 2; | |
| /* etc; edited for brevity */ | |
| We can perhaps better see the code by turning off | |
| :c:macro:`GCC_JIT_BOOL_OPTION_DEBUGINFO` to suppress all those ``DEBUG`` | |
| statements, giving: | |
| .. code-block:: console | |
| $ less /tmp/libgccjit-1Hywc0/fake.c.016t.ssa | |
| .. code-block:: c | |
| ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0) | |
| factorial (signed int arg) | |
| { | |
| signed int stack[8]; | |
| signed int stack_depth; | |
| signed int x; | |
| signed int y; | |
| <unnamed type> _20; | |
| signed int _21; | |
| signed int _38; | |
| signed int _44; | |
| signed int _51; | |
| signed int _56; | |
| initial: | |
| stack_depth_3 = 0; | |
| stack[stack_depth_3] = arg_5(D); | |
| stack_depth_7 = stack_depth_3 + 1; | |
| stack_depth_8 = stack_depth_7 + -1; | |
| x_9 = stack[stack_depth_8]; | |
| stack[stack_depth_8] = x_9; | |
| stack_depth_11 = stack_depth_8 + 1; | |
| stack[stack_depth_11] = x_9; | |
| stack_depth_13 = stack_depth_11 + 1; | |
| stack[stack_depth_13] = 2; | |
| stack_depth_15 = stack_depth_13 + 1; | |
| stack_depth_16 = stack_depth_15 + -1; | |
| y_17 = stack[stack_depth_16]; | |
| stack_depth_18 = stack_depth_16 + -1; | |
| x_19 = stack[stack_depth_18]; | |
| _20 = x_19 < y_17; | |
| _21 = (signed int) _20; | |
| stack[stack_depth_18] = _21; | |
| stack_depth_23 = stack_depth_18 + 1; | |
| stack_depth_24 = stack_depth_23 + -1; | |
| x_25 = stack[stack_depth_24]; | |
| if (x_25 != 0) | |
| goto <bb 4> (instr9); | |
| else | |
| goto <bb 3> (instr4); | |
| instr4: | |
| /* DUP */: | |
| stack_depth_26 = stack_depth_24 + -1; | |
| x_27 = stack[stack_depth_26]; | |
| stack[stack_depth_26] = x_27; | |
| stack_depth_29 = stack_depth_26 + 1; | |
| stack[stack_depth_29] = x_27; | |
| stack_depth_31 = stack_depth_29 + 1; | |
| stack[stack_depth_31] = 1; | |
| stack_depth_33 = stack_depth_31 + 1; | |
| stack_depth_34 = stack_depth_33 + -1; | |
| y_35 = stack[stack_depth_34]; | |
| stack_depth_36 = stack_depth_34 + -1; | |
| x_37 = stack[stack_depth_36]; | |
| _38 = x_37 - y_35; | |
| stack[stack_depth_36] = _38; | |
| stack_depth_40 = stack_depth_36 + 1; | |
| stack_depth_41 = stack_depth_40 + -1; | |
| x_42 = stack[stack_depth_41]; | |
| _44 = factorial (x_42); | |
| stack[stack_depth_41] = _44; | |
| stack_depth_46 = stack_depth_41 + 1; | |
| stack_depth_47 = stack_depth_46 + -1; | |
| y_48 = stack[stack_depth_47]; | |
| stack_depth_49 = stack_depth_47 + -1; | |
| x_50 = stack[stack_depth_49]; | |
| _51 = x_50 * y_48; | |
| stack[stack_depth_49] = _51; | |
| stack_depth_53 = stack_depth_49 + 1; | |
| # stack_depth_1 = PHI <stack_depth_24(2), stack_depth_53(3)> | |
| instr9: | |
| /* RETURN */: | |
| stack_depth_54 = stack_depth_1 + -1; | |
| x_55 = stack[stack_depth_54]; | |
| _56 = x_55; | |
| stack ={v} {CLOBBER}; | |
| return _56; | |
| } | |
| Note in the above how all the :c:type:`gcc_jit_block` instances we | |
| created have been consolidated into just 3 blocks in GCC's internal | |
| representation: ``initial``, ``instr4`` and ``instr9``. | |
| Optimizing away stack manipulation | |
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | |
| Recall our simple implementation of stack operations. Let's examine | |
| how the stack operations are optimized away. | |
| After a pass of constant-propagation, the depth of the stack at each | |
| opcode can be determined at compile-time: | |
| .. code-block:: console | |
| $ less /tmp/libgccjit-1Hywc0/fake.c.021t.ccp1 | |
| .. code-block:: c | |
| ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0) | |
| factorial (signed int arg) | |
| { | |
| signed int stack[8]; | |
| signed int stack_depth; | |
| signed int x; | |
| signed int y; | |
| <unnamed type> _20; | |
| signed int _21; | |
| signed int _38; | |
| signed int _44; | |
| signed int _51; | |
| initial: | |
| stack[0] = arg_5(D); | |
| x_9 = stack[0]; | |
| stack[0] = x_9; | |
| stack[1] = x_9; | |
| stack[2] = 2; | |
| y_17 = stack[2]; | |
| x_19 = stack[1]; | |
| _20 = x_19 < y_17; | |
| _21 = (signed int) _20; | |
| stack[1] = _21; | |
| x_25 = stack[1]; | |
| if (x_25 != 0) | |
| goto <bb 4> (instr9); | |
| else | |
| goto <bb 3> (instr4); | |
| instr4: | |
| /* DUP */: | |
| x_27 = stack[0]; | |
| stack[0] = x_27; | |
| stack[1] = x_27; | |
| stack[2] = 1; | |
| y_35 = stack[2]; | |
| x_37 = stack[1]; | |
| _38 = x_37 - y_35; | |
| stack[1] = _38; | |
| x_42 = stack[1]; | |
| _44 = factorial (x_42); | |
| stack[1] = _44; | |
| y_48 = stack[1]; | |
| x_50 = stack[0]; | |
| _51 = x_50 * y_48; | |
| stack[0] = _51; | |
| instr9: | |
| /* RETURN */: | |
| x_55 = stack[0]; | |
| x_56 = x_55; | |
| stack ={v} {CLOBBER}; | |
| return x_56; | |
| } | |
| Note how, in the above, all those ``stack_depth`` values are now just | |
| constants: we're accessing specific stack locations at each opcode. | |
| The "esra" pass ("Early Scalar Replacement of Aggregates") breaks | |
| out our "stack" array into individual elements: | |
| .. code-block:: console | |
| $ less /tmp/libgccjit-1Hywc0/fake.c.024t.esra | |
| .. code-block:: c | |
| ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0) | |
| Created a replacement for stack offset: 0, size: 32: stack$0 | |
| Created a replacement for stack offset: 32, size: 32: stack$1 | |
| Created a replacement for stack offset: 64, size: 32: stack$2 | |
| Symbols to be put in SSA form | |
| { D.89 D.90 D.91 } | |
| Incremental SSA update started at block: 0 | |
| Number of blocks in CFG: 5 | |
| Number of blocks to update: 4 ( 80%) | |
| factorial (signed int arg) | |
| { | |
| signed int stack$2; | |
| signed int stack$1; | |
| signed int stack$0; | |
| signed int stack[8]; | |
| signed int stack_depth; | |
| signed int x; | |
| signed int y; | |
| <unnamed type> _20; | |
| signed int _21; | |
| signed int _38; | |
| signed int _44; | |
| signed int _51; | |
| initial: | |
| stack$0_45 = arg_5(D); | |
| x_9 = stack$0_45; | |
| stack$0_39 = x_9; | |
| stack$1_32 = x_9; | |
| stack$2_30 = 2; | |
| y_17 = stack$2_30; | |
| x_19 = stack$1_32; | |
| _20 = x_19 < y_17; | |
| _21 = (signed int) _20; | |
| stack$1_28 = _21; | |
| x_25 = stack$1_28; | |
| if (x_25 != 0) | |
| goto <bb 4> (instr9); | |
| else | |
| goto <bb 3> (instr4); | |
| instr4: | |
| /* DUP */: | |
| x_27 = stack$0_39; | |
| stack$0_22 = x_27; | |
| stack$1_14 = x_27; | |
| stack$2_12 = 1; | |
| y_35 = stack$2_12; | |
| x_37 = stack$1_14; | |
| _38 = x_37 - y_35; | |
| stack$1_10 = _38; | |
| x_42 = stack$1_10; | |
| _44 = factorial (x_42); | |
| stack$1_6 = _44; | |
| y_48 = stack$1_6; | |
| x_50 = stack$0_22; | |
| _51 = x_50 * y_48; | |
| stack$0_1 = _51; | |
| # stack$0_52 = PHI <stack$0_39(2), stack$0_1(3)> | |
| instr9: | |
| /* RETURN */: | |
| x_55 = stack$0_52; | |
| x_56 = x_55; | |
| stack ={v} {CLOBBER}; | |
| return x_56; | |
| } | |
| Hence at this point, all those pushes and pops of the stack are now | |
| simply assignments to specific temporary variables. | |
| After some copy propagation, the stack manipulation has been completely | |
| optimized away: | |
| .. code-block:: console | |
| $ less /tmp/libgccjit-1Hywc0/fake.c.026t.copyprop1 | |
| .. code-block:: c | |
| ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0) | |
| factorial (signed int arg) | |
| { | |
| signed int stack$2; | |
| signed int stack$1; | |
| signed int stack$0; | |
| signed int stack[8]; | |
| signed int stack_depth; | |
| signed int x; | |
| signed int y; | |
| <unnamed type> _20; | |
| signed int _21; | |
| signed int _38; | |
| signed int _44; | |
| signed int _51; | |
| initial: | |
| stack$0_39 = arg_5(D); | |
| _20 = arg_5(D) <= 1; | |
| _21 = (signed int) _20; | |
| if (_21 != 0) | |
| goto <bb 4> (instr9); | |
| else | |
| goto <bb 3> (instr4); | |
| instr4: | |
| /* DUP */: | |
| _38 = arg_5(D) + -1; | |
| _44 = factorial (_38); | |
| _51 = arg_5(D) * _44; | |
| stack$0_1 = _51; | |
| # stack$0_52 = PHI <arg_5(D)(2), _51(3)> | |
| instr9: | |
| /* RETURN */: | |
| stack ={v} {CLOBBER}; | |
| return stack$0_52; | |
| } | |
| Later on, another pass finally eliminated ``stack_depth`` local and the | |
| unused parts of the `stack`` array altogether: | |
| .. code-block:: console | |
| $ less /tmp/libgccjit-1Hywc0/fake.c.036t.release_ssa | |
| .. code-block:: c | |
| ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0) | |
| Released 44 names, 314.29%, removed 44 holes | |
| factorial (signed int arg) | |
| { | |
| signed int stack$0; | |
| signed int mult_acc_1; | |
| <unnamed type> _5; | |
| signed int _6; | |
| signed int _7; | |
| signed int mul_tmp_10; | |
| signed int mult_acc_11; | |
| signed int mult_acc_13; | |
| # arg_9 = PHI <arg_8(D)(0)> | |
| # mult_acc_13 = PHI <1(0)> | |
| initial: | |
| <bb 5>: | |
| # arg_4 = PHI <arg_9(2), _7(3)> | |
| # mult_acc_1 = PHI <mult_acc_13(2), mult_acc_11(3)> | |
| _5 = arg_4 <= 1; | |
| _6 = (signed int) _5; | |
| if (_6 != 0) | |
| goto <bb 4> (instr9); | |
| else | |
| goto <bb 3> (instr4); | |
| instr4: | |
| /* DUP */: | |
| _7 = arg_4 + -1; | |
| mult_acc_11 = mult_acc_1 * arg_4; | |
| goto <bb 5>; | |
| # stack$0_12 = PHI <arg_4(5)> | |
| instr9: | |
| /* RETURN */: | |
| mul_tmp_10 = mult_acc_1 * stack$0_12; | |
| return mul_tmp_10; | |
| } | |
| Elimination of tail recursion | |
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | |
| Another significant optimization is the detection that the call to | |
| ``factorial`` is tail recursion, which can be eliminated in favor of | |
| an iteration: | |
| .. code-block:: console | |
| $ less /tmp/libgccjit-1Hywc0/fake.c.030t.tailr1 | |
| .. code-block:: c | |
| ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0) | |
| Symbols to be put in SSA form | |
| { D.88 } | |
| Incremental SSA update started at block: 0 | |
| Number of blocks in CFG: 5 | |
| Number of blocks to update: 4 ( 80%) | |
| factorial (signed int arg) | |
| { | |
| signed int stack$2; | |
| signed int stack$1; | |
| signed int stack$0; | |
| signed int stack[8]; | |
| signed int stack_depth; | |
| signed int x; | |
| signed int y; | |
| signed int mult_acc_1; | |
| <unnamed type> _20; | |
| signed int _21; | |
| signed int _38; | |
| signed int mul_tmp_44; | |
| signed int mult_acc_51; | |
| # arg_5 = PHI <arg_39(D)(0), _38(3)> | |
| # mult_acc_1 = PHI <1(0), mult_acc_51(3)> | |
| initial: | |
| _20 = arg_5 <= 1; | |
| _21 = (signed int) _20; | |
| if (_21 != 0) | |
| goto <bb 4> (instr9); | |
| else | |
| goto <bb 3> (instr4); | |
| instr4: | |
| /* DUP */: | |
| _38 = arg_5 + -1; | |
| mult_acc_51 = mult_acc_1 * arg_5; | |
| goto <bb 2> (initial); | |
| # stack$0_52 = PHI <arg_5(2)> | |
| instr9: | |
| /* RETURN */: | |
| stack ={v} {CLOBBER}; | |
| mul_tmp_44 = mult_acc_1 * stack$0_52; | |
| return mul_tmp_44; | |
| } |