Debian Codegraph @

gcc/jit/docs/cp/intro/tutorial04.rst

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