| 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 |
.. 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 |
} |