Debian Codegraph @

gcc/jit/docs/intro/tutorial04.rst

raw
1 .. Copyright (C) 2014-2025 Free Software Foundation, Inc.
2 Originally contributed by David Malcolm <[email protected]>
3
4 This is free software: you can redistribute it and/or modify it
5 under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see
16 <https://www.gnu.org/licenses/>.
17
18 Tutorial part 4: Adding JIT-compilation to a toy interpreter
19 ------------------------------------------------------------
20 In this example we construct a "toy" interpreter, and add JIT-compilation
21 to it.
22
23 Our toy interpreter
24 *******************
25
26 It's a stack-based interpreter, and is intended as a (very simple) example
27 of the kind of bytecode interpreter seen in dynamic languages such as
28 Python, Ruby etc.
29
30 For the sake of simplicity, our toy virtual machine is very limited:
31
32 * The only data type is `int`
33
34 * It can only work on one function at a time (so that the only
35 function call that can be made is to recurse).
36
37 * Functions can only take one parameter.
38
39 * Functions have a stack of `int` values.
40
41 * We'll implement function call within the interpreter by calling a
42 function in our implementation, rather than implementing our own
43 frame stack.
44
45 * The parser is only good enough to get the examples to work.
46
47 Naturally, a real interpreter would be much more complicated that this.
48
49 The following operations are supported:
50
51 .. list-table::
52 :header-rows: 1
53 :widths: 35 50 25 25
54
55 * - Operation
56 - Meaning
57 - Old Stack
58 - New Stack
59
60 * - DUP
61 - Duplicate top of stack.
62 - ``[..., x]``
63 - ``[..., x, x]``
64 * - ROT
65 - Swap top two elements of stack.
66 - ``[..., x, y]``
67 - ``[..., y, x]``
68 * - BINARY_ADD
69 - Add the top two elements on the stack.
70 - ``[..., x, y]``
71 - ``[..., (x+y)]``
72 * - BINARY_SUBTRACT
73 - Likewise, but subtract.
74 - ``[..., x, y]``
75 - ``[..., (x-y)]``
76 * - BINARY_MULT
77 - Likewise, but multiply.
78 - ``[..., x, y]``
79 - ``[..., (x*y)]``
80 * - BINARY_COMPARE_LT
81 - Compare the top two elements on the stack and push a nonzero/zero if (x<y).
82 - ``[..., x, y]``
83 - ``[..., (x<y)]``
84 * - RECURSE
85 - Recurse, passing the top of the stack, and popping the result.
86 - ``[..., x]``
87 - ``[..., fn(x)]``
88 * - RETURN
89 - Return the top of the stack.
90 - ``[x]``
91 - ``[]``
92 * - PUSH_CONST `arg`
93 - Push an int const.
94 - ``[...]``
95 - ``[..., arg]``
96 * - JUMP_ABS_IF_TRUE `arg`
97 - Pop; if top of stack was nonzero, jump to ``arg``.
98 - ``[..., x]``
99 - ``[...]``
100
101 Programs can be interpreted, disassembled, and compiled to machine code.
102
103 The interpreter reads ``.toy`` scripts. Here's what a simple recursive
104 factorial program looks like, the script ``factorial.toy``.
105 The parser ignores lines beginning with a `#`.
106
107 .. literalinclude:: ../examples/tut04-toyvm/factorial.toy
108 :lines: 1-
109 :language: c
110
111 The interpreter is a simple infinite loop with a big ``switch`` statement
112 based on what the next opcode is:
113
114 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
115 :start-after: /* Execute the given function. */
116 :end-before: /* JIT compilation. */
117 :language: c
118
119 Compiling to machine code
120 *************************
121 We want to generate machine code that can be cast to this type and
122 then directly executed in-process:
123
124 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
125 :start-after: /* Functions are compiled to this function ptr type. */
126 :end-before: enum opcode
127 :language: c
128
129 The lifetime of the code is tied to that of a :c:expr:`gcc_jit_result *`.
130 We'll handle this by bundling them up in a structure, so that we can
131 clean them up together by calling :c:func:`gcc_jit_result_release`:
132
133 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
134 :start-after: /* A struct to hold the compilation results. */
135 :end-before: /* The main compilation hook. */
136 :language: c
137
138 Our compiler isn't very sophisticated; it takes the implementation of
139 each opcode above, and maps it directly to the operations supported by
140 the libgccjit API.
141
142 How should we handle the stack? In theory we could calculate what the
143 stack depth will be at each opcode, and optimize away the stack
144 manipulation "by hand". We'll see below that libgccjit is able to do
145 this for us, so we'll implement stack manipulation
146 in a direct way, by creating a ``stack`` array and ``stack_depth``
147 variables, local within the generated function, equivalent to this C code:
148
149 .. code-block:: c
150
151 int stack_depth;
152 int stack[MAX_STACK_DEPTH];
153
154 We'll also have local variables ``x`` and ``y`` for use when implementing
155 the opcodes, equivalent to this:
156
157 .. code-block:: c
158
159 int x;
160 int y;
161
162 This means our compiler has the following state:
163
164 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
165 :start-after: /* JIT compilation. */
166 :end-before: /* Stack manipulation. */
167 :language: c
168
169 Setting things up
170 *****************
171
172 First we create our types:
173
174 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
175 :start-after: /* Create types. */
176 :end-before: /* The constant value 1. */
177 :language: c
178
179 along with extracting a useful `int` constant:
180
181 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
182 :start-after: /* The constant value 1. */
183 :end-before: /* Create locations. */
184 :language: c
185
186 We'll implement push and pop in terms of the ``stack`` array and
187 ``stack_depth``. Here are helper functions for adding statements to
188 a block, implementing pushing and popping values:
189
190 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
191 :start-after: /* Stack manipulation. */
192 :end-before: /* A struct to hold the compilation results. */
193 :language: c
194
195 We will support single-stepping through the generated code in the
196 debugger, so we need to create :c:type:`gcc_jit_location` instances, one
197 per operation in the source code. These will reference the lines of
198 e.g. ``factorial.toy``.
199
200 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
201 :start-after: /* Create locations. */
202 :end-before: /* Creating the function. */
203 :language: c
204
205 Let's create the function itself. As usual, we create its parameter
206 first, then use the parameter to create the function:
207
208 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
209 :start-after: /* Creating the function. */
210 :end-before: /* Create stack lvalues. */
211 :language: c
212
213 We create the locals within the function.
214
215 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
216 :start-after: /* Create stack lvalues. */
217 :end-before: /* 1st pass: create blocks, one per opcode.
218 :language: c
219
220 Populating the function
221 ***********************
222
223 There's some one-time initialization, and the API treats the first block
224 you create as the entrypoint of the function, so we need to create that
225 block first:
226
227 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
228 :start-after: first. */
229 :end-before: /* Create a block per operation. */
230 :language: c
231
232 We can now create blocks for each of the operations. Most of these will
233 be consolidated into larger blocks when the optimizer runs.
234
235 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
236 :start-after: /* Create a block per operation. */
237 :end-before: /* Populate the initial block. */
238 :language: c
239
240 Now that we have a block it can jump to when it's done, we can populate
241 the initial block:
242
243 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
244 :start-after: /* Populate the initial block. */
245 :end-before: /* 2nd pass: fill in instructions. */
246 :language: c
247
248 We can now populate the blocks for the individual operations. We loop
249 through them, adding instructions to their blocks:
250
251 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
252 :start-after: /* 2nd pass: fill in instructions. */
253 :end-before: /* Helper macros. */
254 :language: c
255
256 We're going to have another big ``switch`` statement for implementing
257 the opcodes, this time for compiling them, rather than interpreting
258 them. It's helpful to have macros for implementing push and pop, so that
259 we can make the ``switch`` statement that's coming up look as much as
260 possible like the one above within the interpreter:
261
262 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
263 :start-after: /* Helper macros. */
264 :end-before: gcc_jit_block_add_comment
265 :language: c
266
267 .. note::
268
269 A particularly clever implementation would have an *identical*
270 ``switch`` statement shared by the interpreter and the compiler, with
271 some preprocessor "magic". We're not doing that here, for the sake
272 of simplicity.
273
274 When I first implemented this compiler, I accidentally missed an edit
275 when copying and pasting the ``Y_EQUALS_POP`` macro, so that popping the
276 stack into ``y`` instead erroneously assigned it to ``x``, leaving ``y``
277 uninitialized.
278
279 To track this kind of thing down, we can use
280 :c:func:`gcc_jit_block_add_comment` to add descriptive comments
281 to the internal representation. This is invaluable when looking through
282 the generated IR for, say ``factorial``:
283
284 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
285 :start-after: PUSH_RVALUE (gcc_jit_lvalue_as_rvalue (state.y))
286 :end-before: /* Handle the individual opcodes. */
287 :language: c
288
289 We can now write the big ``switch`` statement that implements the
290 individual opcodes, populating the relevant block with statements:
291
292 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
293 :start-after: /* Handle the individual opcodes. */
294 :end-before: /* Go to the next block. */
295 :language: c
296
297 Every block must be terminated, via a call to one of the
298 ``gcc_jit_block_end_with_`` entrypoints. This has been done for two
299 of the opcodes, but we need to do it for the other ones, by jumping
300 to the next block.
301
302 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
303 :start-after: /* Go to the next block. */
304 :end-before: /* end of loop on PC locations. */
305 :language: c
306
307 This is analogous to simply incrementing the program counter.
308
309 Verifying the control flow graph
310 ********************************
311 Having finished looping over the blocks, the context is complete.
312
313 As before, we can verify that the control flow and statements are sane by
314 using :c:func:`gcc_jit_function_dump_to_dot`:
315
316 .. code-block:: c
317
318 gcc_jit_function_dump_to_dot (state.fn, "/tmp/factorial.dot");
319
320 and viewing the result. Note how the label names, comments, and
321 variable names show up in the dump, to make it easier to spot
322 errors in our compiler.
323
324 .. figure:: factorial.png
325 :alt: image of a control flow graph
326
327 Compiling the context
328 *********************
329 Having finished looping over the blocks and populating them with
330 statements, the context is complete.
331
332 We can now compile it, and extract machine code from the result:
333
334 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
335 :start-after: /* We've now finished populating the context. Compile it. */
336 :end-before: /* (this leaks "jit_result" and "funcname") */
337 :language: c
338
339 We can now run the result:
340
341 .. literalinclude:: ../examples/tut04-toyvm/toyvm.c
342 :start-after: /* JIT-compilation. */
343 :end-before: return 0;
344 :language: c
345
346 Single-stepping through the generated code
347 ******************************************
348
349 It's possible to debug the generated code. To do this we need to both:
350
351 * Set up source code locations for our statements, so that we can
352 meaningfully step through the code. We did this above by
353 calling :c:func:`gcc_jit_context_new_location` and using the
354 results.
355
356 * Enable the generation of debugging information, by setting
357 :c:macro:`GCC_JIT_BOOL_OPTION_DEBUGINFO` on the
358 :c:type:`gcc_jit_context` via
359 :c:func:`gcc_jit_context_set_bool_option`:
360
361 .. code-block:: c
362
363 gcc_jit_context_set_bool_option (
364 ctxt,
365 GCC_JIT_BOOL_OPTION_DEBUGINFO,
366 1);
367
368 Having done this, we can put a breakpoint on the generated function:
369
370 .. code-block:: console
371
372 $ gdb --args ./toyvm factorial.toy 10
373 (gdb) break factorial
374 Function "factorial" not defined.
375 Make breakpoint pending on future shared library load? (y or [n]) y
376 Breakpoint 1 (factorial) pending.
377 (gdb) run
378 Breakpoint 1, factorial (arg=10) at factorial.toy:14
379 14 DUP
380
381 We've set up location information, which references ``factorial.toy``.
382 This allows us to use e.g. ``list`` to see where we are in the script:
383
384 .. code-block:: console
385
386 (gdb) list
387 9
388 10 # Initial state:
389 11 # stack: [arg]
390 12
391 13 # 0:
392 14 DUP
393 15 # stack: [arg, arg]
394 16
395 17 # 1:
396 18 PUSH_CONST 2
397
398 and to step through the function, examining the data:
399
400 .. code-block:: console
401
402 (gdb) n
403 18 PUSH_CONST 2
404 (gdb) n
405 22 BINARY_COMPARE_LT
406 (gdb) print stack
407 $5 = {10, 10, 2, 0, -7152, 32767, 0, 0}
408 (gdb) print stack_depth
409 $6 = 3
410
411 You'll see that the parts of the ``stack`` array that haven't been
412 touched yet are uninitialized.
413
414 .. note::
415
416 Turning on optimizations may lead to unpredictable results when
417 stepping through the generated code: the execution may appear to
418 "jump around" the source code. This is analogous to turning up the
419 optimization level in a regular compiler.
420
421 Examining the generated code
422 ****************************
423
424 How good is the optimized code?
425
426 We can turn up optimizations, by calling
427 :c:func:`gcc_jit_context_set_int_option` with
428 :c:macro:`GCC_JIT_INT_OPTION_OPTIMIZATION_LEVEL`:
429
430 .. code-block:: c
431
432 gcc_jit_context_set_int_option (
433 ctxt,
434 GCC_JIT_INT_OPTION_OPTIMIZATION_LEVEL,
435 3);
436
437 One of GCC's internal representations is called "gimple". A dump of the
438 initial gimple representation of the code can be seen by setting:
439
440 .. code-block:: c
441
442 gcc_jit_context_set_bool_option (ctxt,
443 GCC_JIT_BOOL_OPTION_DUMP_INITIAL_GIMPLE,
444 1);
445
446 With optimization on and source locations displayed, this gives:
447
448 .. We'll use "c" for gimple dumps
449
450 .. code-block:: c
451
452 factorial (signed int arg)
453 {
454 <unnamed type> D.80;
455 signed int D.81;
456 signed int D.82;
457 signed int D.83;
458 signed int D.84;
459 signed int D.85;
460 signed int y;
461 signed int x;
462 signed int stack_depth;
463 signed int stack[8];
464
465 try
466 {
467 initial:
468 stack_depth = 0;
469 stack[stack_depth] = arg;
470 stack_depth = stack_depth + 1;
471 goto instr0;
472 instr0:
473 /* DUP */:
474 stack_depth = stack_depth + -1;
475 x = stack[stack_depth];
476 stack[stack_depth] = x;
477 stack_depth = stack_depth + 1;
478 stack[stack_depth] = x;
479 stack_depth = stack_depth + 1;
480 goto instr1;
481 instr1:
482 /* PUSH_CONST */:
483 stack[stack_depth] = 2;
484 stack_depth = stack_depth + 1;
485 goto instr2;
486
487 /* etc */
488
489 You can see the generated machine code in assembly form via:
490
491 .. code-block:: c
492
493 gcc_jit_context_set_bool_option (
494 ctxt,
495 GCC_JIT_BOOL_OPTION_DUMP_GENERATED_CODE,
496 1);
497 result = gcc_jit_context_compile (ctxt);
498
499 which shows that (on this x86_64 box) the compiler has unrolled the loop
500 and is using MMX instructions to perform several multiplications
501 simultaneously:
502
503 .. code-block:: gas
504
505 .file "fake.c"
506 .text
507 .Ltext0:
508 .p2align 4,,15
509 .globl factorial
510 .type factorial, @function
511 factorial:
512 .LFB0:
513 .file 1 "factorial.toy"
514 .loc 1 14 0
515 .cfi_startproc
516 .LVL0:
517 .L2:
518 .loc 1 26 0
519 cmpl $1, %edi
520 jle .L13
521 leal -1(%rdi), %edx
522 movl %edx, %ecx
523 shrl $2, %ecx
524 leal 0(,%rcx,4), %esi
525 testl %esi, %esi
526 je .L14
527 cmpl $9, %edx
528 jbe .L14
529 leal -2(%rdi), %eax
530 movl %eax, -16(%rsp)
531 leal -3(%rdi), %eax
532 movd -16(%rsp), %xmm0
533 movl %edi, -16(%rsp)
534 movl %eax, -12(%rsp)
535 movd -16(%rsp), %xmm1
536 xorl %eax, %eax
537 movl %edx, -16(%rsp)
538 movd -12(%rsp), %xmm4
539 movd -16(%rsp), %xmm6
540 punpckldq %xmm4, %xmm0
541 movdqa .LC1(%rip), %xmm4
542 punpckldq %xmm6, %xmm1
543 punpcklqdq %xmm0, %xmm1
544 movdqa .LC0(%rip), %xmm0
545 jmp .L5
546 # etc - edited for brevity
547
548 This is clearly overkill for a function that will likely overflow the
549 ``int`` type before the vectorization is worthwhile - but then again, this
550 is a toy example.
551
552 Turning down the optimization level to 2:
553
554 .. code-block:: c
555
556 gcc_jit_context_set_int_option (
557 ctxt,
558 GCC_JIT_INT_OPTION_OPTIMIZATION_LEVEL,
559 3);
560
561 yields this code, which is simple enough to quote in its entirety:
562
563 .. code-block:: gas
564
565 .file "fake.c"
566 .text
567 .p2align 4,,15
568 .globl factorial
569 .type factorial, @function
570 factorial:
571 .LFB0:
572 .cfi_startproc
573 .L2:
574 cmpl $1, %edi
575 jle .L8
576 movl $1, %edx
577 jmp .L4
578 .p2align 4,,10
579 .p2align 3
580 .L6:
581 movl %eax, %edi
582 .L4:
583 .L5:
584 leal -1(%rdi), %eax
585 imull %edi, %edx
586 cmpl $1, %eax
587 jne .L6
588 .L3:
589 .L7:
590 imull %edx, %eax
591 ret
592 .L8:
593 movl %edi, %eax
594 movl $1, %edx
595 jmp .L7
596 .cfi_endproc
597 .LFE0:
598 .size factorial, .-factorial
599 .ident "GCC: (GNU) 4.9.0 20131023 (Red Hat 0.2)"
600 .section .note.GNU-stack,"",@progbits
601
602 Note that the stack pushing and popping have been eliminated, as has the
603 recursive call (in favor of an iteration).
604
605 Putting it all together
606 ***********************
607
608 The complete example can be seen in the source tree at
609 ``gcc/jit/docs/examples/tut04-toyvm/toyvm.c``
610
611 along with a Makefile and a couple of sample .toy scripts:
612
613 .. code-block:: console
614
615 $ ls -al
616 drwxrwxr-x. 2 david david 4096 Sep 19 17:46 .
617 drwxrwxr-x. 3 david david 4096 Sep 19 15:26 ..
618 -rw-rw-r--. 1 david david 615 Sep 19 12:43 factorial.toy
619 -rw-rw-r--. 1 david david 834 Sep 19 13:08 fibonacci.toy
620 -rw-rw-r--. 1 david david 238 Sep 19 14:22 Makefile
621 -rw-rw-r--. 1 david david 16457 Sep 19 17:07 toyvm.c
622
623 $ make toyvm
624 g++ -Wall -g -o toyvm toyvm.c -lgccjit
625
626 $ ./toyvm factorial.toy 10
627 interpreter result: 3628800
628 compiler result: 3628800
629
630 $ ./toyvm fibonacci.toy 10
631 interpreter result: 55
632 compiler result: 55
633
634 Behind the curtain: How does our code get optimized?
635 ****************************************************
636
637 Our example is done, but you may be wondering about exactly how the
638 compiler turned what we gave it into the machine code seen above.
639
640 We can examine what the compiler is doing in detail by setting:
641
642 .. code-block:: c
643
644 gcc_jit_context_set_bool_option (state.ctxt,
645 GCC_JIT_BOOL_OPTION_DUMP_EVERYTHING,
646 1);
647 gcc_jit_context_set_bool_option (state.ctxt,
648 GCC_JIT_BOOL_OPTION_KEEP_INTERMEDIATES,
649 1);
650
651 This will dump detailed information about the compiler's state to a
652 directory under ``/tmp``, and keep it from being cleaned up.
653
654 The precise names and their formats of these files is subject to change.
655 Higher optimization levels lead to more files.
656 Here's what I saw (edited for brevity; there were almost 200 files):
657
658 .. code-block:: console
659
660 intermediate files written to /tmp/libgccjit-KPQbGw
661 $ ls /tmp/libgccjit-KPQbGw/
662 fake.c.000i.cgraph
663 fake.c.000i.type-inheritance
664 fake.c.004t.gimple
665 fake.c.007t.omplower
666 fake.c.008t.lower
667 fake.c.011t.eh
668 fake.c.012t.cfg
669 fake.c.014i.visibility
670 fake.c.015i.early_local_cleanups
671 fake.c.016t.ssa
672 # etc
673
674 The gimple code is converted into Static Single Assignment form,
675 with annotations for use when generating the debuginfo:
676
677 .. code-block:: console
678
679 $ less /tmp/libgccjit-KPQbGw/fake.c.016t.ssa
680
681 .. code-block:: c
682
683 ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0)
684
685 factorial (signed int arg)
686 {
687 signed int stack[8];
688 signed int stack_depth;
689 signed int x;
690 signed int y;
691 <unnamed type> _20;
692 signed int _21;
693 signed int _38;
694 signed int _44;
695 signed int _51;
696 signed int _56;
697
698 initial:
699 stack_depth_3 = 0;
700 # DEBUG stack_depth => stack_depth_3
701 stack[stack_depth_3] = arg_5(D);
702 stack_depth_7 = stack_depth_3 + 1;
703 # DEBUG stack_depth => stack_depth_7
704 # DEBUG instr0 => NULL
705 # DEBUG /* DUP */ => NULL
706 stack_depth_8 = stack_depth_7 + -1;
707 # DEBUG stack_depth => stack_depth_8
708 x_9 = stack[stack_depth_8];
709 # DEBUG x => x_9
710 stack[stack_depth_8] = x_9;
711 stack_depth_11 = stack_depth_8 + 1;
712 # DEBUG stack_depth => stack_depth_11
713 stack[stack_depth_11] = x_9;
714 stack_depth_13 = stack_depth_11 + 1;
715 # DEBUG stack_depth => stack_depth_13
716 # DEBUG instr1 => NULL
717 # DEBUG /* PUSH_CONST */ => NULL
718 stack[stack_depth_13] = 2;
719
720 /* etc; edited for brevity */
721
722 We can perhaps better see the code by turning off
723 :c:macro:`GCC_JIT_BOOL_OPTION_DEBUGINFO` to suppress all those ``DEBUG``
724 statements, giving:
725
726 .. code-block:: console
727
728 $ less /tmp/libgccjit-1Hywc0/fake.c.016t.ssa
729
730 .. code-block:: c
731
732 ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0)
733
734 factorial (signed int arg)
735 {
736 signed int stack[8];
737 signed int stack_depth;
738 signed int x;
739 signed int y;
740 <unnamed type> _20;
741 signed int _21;
742 signed int _38;
743 signed int _44;
744 signed int _51;
745 signed int _56;
746
747 initial:
748 stack_depth_3 = 0;
749 stack[stack_depth_3] = arg_5(D);
750 stack_depth_7 = stack_depth_3 + 1;
751 stack_depth_8 = stack_depth_7 + -1;
752 x_9 = stack[stack_depth_8];
753 stack[stack_depth_8] = x_9;
754 stack_depth_11 = stack_depth_8 + 1;
755 stack[stack_depth_11] = x_9;
756 stack_depth_13 = stack_depth_11 + 1;
757 stack[stack_depth_13] = 2;
758 stack_depth_15 = stack_depth_13 + 1;
759 stack_depth_16 = stack_depth_15 + -1;
760 y_17 = stack[stack_depth_16];
761 stack_depth_18 = stack_depth_16 + -1;
762 x_19 = stack[stack_depth_18];
763 _20 = x_19 < y_17;
764 _21 = (signed int) _20;
765 stack[stack_depth_18] = _21;
766 stack_depth_23 = stack_depth_18 + 1;
767 stack_depth_24 = stack_depth_23 + -1;
768 x_25 = stack[stack_depth_24];
769 if (x_25 != 0)
770 goto <bb 4> (instr9);
771 else
772 goto <bb 3> (instr4);
773
774 instr4:
775 /* DUP */:
776 stack_depth_26 = stack_depth_24 + -1;
777 x_27 = stack[stack_depth_26];
778 stack[stack_depth_26] = x_27;
779 stack_depth_29 = stack_depth_26 + 1;
780 stack[stack_depth_29] = x_27;
781 stack_depth_31 = stack_depth_29 + 1;
782 stack[stack_depth_31] = 1;
783 stack_depth_33 = stack_depth_31 + 1;
784 stack_depth_34 = stack_depth_33 + -1;
785 y_35 = stack[stack_depth_34];
786 stack_depth_36 = stack_depth_34 + -1;
787 x_37 = stack[stack_depth_36];
788 _38 = x_37 - y_35;
789 stack[stack_depth_36] = _38;
790 stack_depth_40 = stack_depth_36 + 1;
791 stack_depth_41 = stack_depth_40 + -1;
792 x_42 = stack[stack_depth_41];
793 _44 = factorial (x_42);
794 stack[stack_depth_41] = _44;
795 stack_depth_46 = stack_depth_41 + 1;
796 stack_depth_47 = stack_depth_46 + -1;
797 y_48 = stack[stack_depth_47];
798 stack_depth_49 = stack_depth_47 + -1;
799 x_50 = stack[stack_depth_49];
800 _51 = x_50 * y_48;
801 stack[stack_depth_49] = _51;
802 stack_depth_53 = stack_depth_49 + 1;
803
804 # stack_depth_1 = PHI <stack_depth_24(2), stack_depth_53(3)>
805 instr9:
806 /* RETURN */:
807 stack_depth_54 = stack_depth_1 + -1;
808 x_55 = stack[stack_depth_54];
809 _56 = x_55;
810 stack ={v} {CLOBBER};
811 return _56;
812
813 }
814
815 Note in the above how all the :c:type:`gcc_jit_block` instances we
816 created have been consolidated into just 3 blocks in GCC's internal
817 representation: ``initial``, ``instr4`` and ``instr9``.
818
819 Optimizing away stack manipulation
820 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
821 Recall our simple implementation of stack operations. Let's examine
822 how the stack operations are optimized away.
823
824 After a pass of constant-propagation, the depth of the stack at each
825 opcode can be determined at compile-time:
826
827 .. code-block:: console
828
829 $ less /tmp/libgccjit-1Hywc0/fake.c.021t.ccp1
830
831 .. code-block:: c
832
833 ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0)
834
835 factorial (signed int arg)
836 {
837 signed int stack[8];
838 signed int stack_depth;
839 signed int x;
840 signed int y;
841 <unnamed type> _20;
842 signed int _21;
843 signed int _38;
844 signed int _44;
845 signed int _51;
846
847 initial:
848 stack[0] = arg_5(D);
849 x_9 = stack[0];
850 stack[0] = x_9;
851 stack[1] = x_9;
852 stack[2] = 2;
853 y_17 = stack[2];
854 x_19 = stack[1];
855 _20 = x_19 < y_17;
856 _21 = (signed int) _20;
857 stack[1] = _21;
858 x_25 = stack[1];
859 if (x_25 != 0)
860 goto <bb 4> (instr9);
861 else
862 goto <bb 3> (instr4);
863
864 instr4:
865 /* DUP */:
866 x_27 = stack[0];
867 stack[0] = x_27;
868 stack[1] = x_27;
869 stack[2] = 1;
870 y_35 = stack[2];
871 x_37 = stack[1];
872 _38 = x_37 - y_35;
873 stack[1] = _38;
874 x_42 = stack[1];
875 _44 = factorial (x_42);
876 stack[1] = _44;
877 y_48 = stack[1];
878 x_50 = stack[0];
879 _51 = x_50 * y_48;
880 stack[0] = _51;
881
882 instr9:
883 /* RETURN */:
884 x_55 = stack[0];
885 x_56 = x_55;
886 stack ={v} {CLOBBER};
887 return x_56;
888
889 }
890
891 Note how, in the above, all those ``stack_depth`` values are now just
892 constants: we're accessing specific stack locations at each opcode.
893
894 The "esra" pass ("Early Scalar Replacement of Aggregates") breaks
895 out our "stack" array into individual elements:
896
897 .. code-block:: console
898
899 $ less /tmp/libgccjit-1Hywc0/fake.c.024t.esra
900
901 .. code-block:: c
902
903 ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0)
904
905 Created a replacement for stack offset: 0, size: 32: stack$0
906 Created a replacement for stack offset: 32, size: 32: stack$1
907 Created a replacement for stack offset: 64, size: 32: stack$2
908
909 Symbols to be put in SSA form
910 { D.89 D.90 D.91 }
911 Incremental SSA update started at block: 0
912 Number of blocks in CFG: 5
913 Number of blocks to update: 4 ( 80%)
914
915
916 factorial (signed int arg)
917 {
918 signed int stack$2;
919 signed int stack$1;
920 signed int stack$0;
921 signed int stack[8];
922 signed int stack_depth;
923 signed int x;
924 signed int y;
925 <unnamed type> _20;
926 signed int _21;
927 signed int _38;
928 signed int _44;
929 signed int _51;
930
931 initial:
932 stack$0_45 = arg_5(D);
933 x_9 = stack$0_45;
934 stack$0_39 = x_9;
935 stack$1_32 = x_9;
936 stack$2_30 = 2;
937 y_17 = stack$2_30;
938 x_19 = stack$1_32;
939 _20 = x_19 < y_17;
940 _21 = (signed int) _20;
941 stack$1_28 = _21;
942 x_25 = stack$1_28;
943 if (x_25 != 0)
944 goto <bb 4> (instr9);
945 else
946 goto <bb 3> (instr4);
947
948 instr4:
949 /* DUP */:
950 x_27 = stack$0_39;
951 stack$0_22 = x_27;
952 stack$1_14 = x_27;
953 stack$2_12 = 1;
954 y_35 = stack$2_12;
955 x_37 = stack$1_14;
956 _38 = x_37 - y_35;
957 stack$1_10 = _38;
958 x_42 = stack$1_10;
959 _44 = factorial (x_42);
960 stack$1_6 = _44;
961 y_48 = stack$1_6;
962 x_50 = stack$0_22;
963 _51 = x_50 * y_48;
964 stack$0_1 = _51;
965
966 # stack$0_52 = PHI <stack$0_39(2), stack$0_1(3)>
967 instr9:
968 /* RETURN */:
969 x_55 = stack$0_52;
970 x_56 = x_55;
971 stack ={v} {CLOBBER};
972 return x_56;
973
974 }
975
976 Hence at this point, all those pushes and pops of the stack are now
977 simply assignments to specific temporary variables.
978
979 After some copy propagation, the stack manipulation has been completely
980 optimized away:
981
982 .. code-block:: console
983
984 $ less /tmp/libgccjit-1Hywc0/fake.c.026t.copyprop1
985
986 .. code-block:: c
987
988 ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0)
989
990 factorial (signed int arg)
991 {
992 signed int stack$2;
993 signed int stack$1;
994 signed int stack$0;
995 signed int stack[8];
996 signed int stack_depth;
997 signed int x;
998 signed int y;
999 <unnamed type> _20;
1000 signed int _21;
1001 signed int _38;
1002 signed int _44;
1003 signed int _51;
1004
1005 initial:
1006 stack$0_39 = arg_5(D);
1007 _20 = arg_5(D) <= 1;
1008 _21 = (signed int) _20;
1009 if (_21 != 0)
1010 goto <bb 4> (instr9);
1011 else
1012 goto <bb 3> (instr4);
1013
1014 instr4:
1015 /* DUP */:
1016 _38 = arg_5(D) + -1;
1017 _44 = factorial (_38);
1018 _51 = arg_5(D) * _44;
1019 stack$0_1 = _51;
1020
1021 # stack$0_52 = PHI <arg_5(D)(2), _51(3)>
1022 instr9:
1023 /* RETURN */:
1024 stack ={v} {CLOBBER};
1025 return stack$0_52;
1026
1027 }
1028
1029 Later on, another pass finally eliminated ``stack_depth`` local and the
1030 unused parts of the `stack`` array altogether:
1031
1032 .. code-block:: console
1033
1034 $ less /tmp/libgccjit-1Hywc0/fake.c.036t.release_ssa
1035
1036 .. code-block:: c
1037
1038 ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0)
1039
1040 Released 44 names, 314.29%, removed 44 holes
1041 factorial (signed int arg)
1042 {
1043 signed int stack$0;
1044 signed int mult_acc_1;
1045 <unnamed type> _5;
1046 signed int _6;
1047 signed int _7;
1048 signed int mul_tmp_10;
1049 signed int mult_acc_11;
1050 signed int mult_acc_13;
1051
1052 # arg_9 = PHI <arg_8(D)(0)>
1053 # mult_acc_13 = PHI <1(0)>
1054 initial:
1055
1056 <bb 5>:
1057 # arg_4 = PHI <arg_9(2), _7(3)>
1058 # mult_acc_1 = PHI <mult_acc_13(2), mult_acc_11(3)>
1059 _5 = arg_4 <= 1;
1060 _6 = (signed int) _5;
1061 if (_6 != 0)
1062 goto <bb 4> (instr9);
1063 else
1064 goto <bb 3> (instr4);
1065
1066 instr4:
1067 /* DUP */:
1068 _7 = arg_4 + -1;
1069 mult_acc_11 = mult_acc_1 * arg_4;
1070 goto <bb 5>;
1071
1072 # stack$0_12 = PHI <arg_4(5)>
1073 instr9:
1074 /* RETURN */:
1075 mul_tmp_10 = mult_acc_1 * stack$0_12;
1076 return mul_tmp_10;
1077
1078 }
1079
1080
1081 Elimination of tail recursion
1082 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1083 Another significant optimization is the detection that the call to
1084 ``factorial`` is tail recursion, which can be eliminated in favor of
1085 an iteration:
1086
1087 .. code-block:: console
1088
1089 $ less /tmp/libgccjit-1Hywc0/fake.c.030t.tailr1
1090
1091 .. code-block:: c
1092
1093 ;; Function factorial (factorial, funcdef_no=0, decl_uid=53, symbol_order=0)
1094
1095
1096 Symbols to be put in SSA form
1097 { D.88 }
1098 Incremental SSA update started at block: 0
1099 Number of blocks in CFG: 5
1100 Number of blocks to update: 4 ( 80%)
1101
1102
1103 factorial (signed int arg)
1104 {
1105 signed int stack$2;
1106 signed int stack$1;
1107 signed int stack$0;
1108 signed int stack[8];
1109 signed int stack_depth;
1110 signed int x;
1111 signed int y;
1112 signed int mult_acc_1;
1113 <unnamed type> _20;
1114 signed int _21;
1115 signed int _38;
1116 signed int mul_tmp_44;
1117 signed int mult_acc_51;
1118
1119 # arg_5 = PHI <arg_39(D)(0), _38(3)>
1120 # mult_acc_1 = PHI <1(0), mult_acc_51(3)>
1121 initial:
1122 _20 = arg_5 <= 1;
1123 _21 = (signed int) _20;
1124 if (_21 != 0)
1125 goto <bb 4> (instr9);
1126 else
1127 goto <bb 3> (instr4);
1128
1129 instr4:
1130 /* DUP */:
1131 _38 = arg_5 + -1;
1132 mult_acc_51 = mult_acc_1 * arg_5;
1133 goto <bb 2> (initial);
1134
1135 # stack$0_52 = PHI <arg_5(2)>
1136 instr9:
1137 /* RETURN */:
1138 stack ={v} {CLOBBER};
1139 mul_tmp_44 = mult_acc_1 * stack$0_52;
1140 return mul_tmp_44;
1141
1142 }