gcc/jit/docs/intro/tutorial03.rst

   1 .. Copyright (C) 2014-2015 Free Software Foundation, Inc.
   2    Originally contributed by David Malcolm <dmalcolm@redhat.com>
   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    <http://www.gnu.org/licenses/>.
  17
  18 Tutorial part 3: Loops and variables
  19 ------------------------------------
  20 Consider this C function:
  21
  22  .. code-block:: c
  23
  24   int loop_test (int n)
  25   {
  26     int sum = 0;
  27     for (int i = 0; i < n; i++)
  28       sum += i * i;
  29     return sum;
  30   }
  31
  32 This example demonstrates some more features of libgccjit, with local
  33 variables and a loop.
  34
  35 To break this down into libgccjit terms, it's usually easier to reword
  36 the `for` loop as a `while` loop, giving:
  37
  38  .. code-block:: c
  39
  40   int loop_test (int n)
  41   {
  42     int sum = 0;
  43     int i = 0;
  44     while (i < n)
  45     {
  46       sum += i * i;
  47       i++;
  48     }
  49     return sum;
  50   }
  51
  52 Here's what the final control flow graph will look like:
  53
  54     .. figure:: sum-of-squares.png
  55       :alt: image of a control flow graph
  56
  57 As before, we include the libgccjit header and make a
  58 :c:type:`gcc_jit_context *`.
  59
  60 .. code-block:: c
  61
  62   #include <libgccjit.h>
  63
  64   void test (void)
  65   {
  66     gcc_jit_context *ctxt;
  67     ctxt = gcc_jit_context_acquire ();
  68
  69 The function works with the C `int` type:
  70
  71 .. code-block:: c
  72
  73   gcc_jit_type *the_type =
  74     gcc_jit_context_get_type (ctxt, GCC_JIT_TYPE_INT);
  75   gcc_jit_type *return_type = the_type;
  76
  77 though we could equally well make it work on, say, `double`:
  78
  79 .. code-block:: c
  80
  81   gcc_jit_type *the_type =
  82     gcc_jit_context_get_type (ctxt, GCC_JIT_TYPE_DOUBLE);
  83
  84 Let's build the function:
  85
  86 .. code-block:: c
  87
  88   gcc_jit_param *n =
  89     gcc_jit_context_new_param (ctxt, NULL, the_type, "n");
  90   gcc_jit_param *params[1] = {n};
  91   gcc_jit_function *func =
  92     gcc_jit_context_new_function (ctxt, NULL,
  93                                   GCC_JIT_FUNCTION_EXPORTED,
  94                                   return_type,
  95                                   "loop_test",
  96                                   1, params, 0);
  97
  98 Expressions: lvalues and rvalues
  99 ********************************
 100
 101 The base class of expression is the :c:type:`gcc_jit_rvalue *`,
 102 representing an expression that can be on the *right*-hand side of
 103 an assignment: a value that can be computed somehow, and assigned
 104 *to* a storage area (such as a variable).  It has a specific
 105 :c:type:`gcc_jit_type *`.
 106
 107 Anothe important class is :c:type:`gcc_jit_lvalue *`.
 108 A :c:type:`gcc_jit_lvalue *`. is something that can of the *left*-hand
 109 side of an assignment: a storage area (such as a variable).
 110
 111 In other words, every assignment can be thought of as:
 112
 113 .. code-block:: c
 114
 115    LVALUE = RVALUE;
 116
 117 Note that :c:type:`gcc_jit_lvalue *` is a subclass of
 118 :c:type:`gcc_jit_rvalue *`, where in an assignment of the form:
 119
 120 .. code-block:: c
 121
 122    LVALUE_A = LVALUE_B;
 123
 124 the `LVALUE_B` implies reading the current value of that storage
 125 area, assigning it into the `LVALUE_A`.
 126
 127 So far the only expressions we've seen are `i * i`:
 128
 129 .. code-block:: c
 130
 131    gcc_jit_rvalue *expr =
 132      gcc_jit_context_new_binary_op (
 133        ctxt, NULL,
 134        GCC_JIT_BINARY_OP_MULT, int_type,
 135        gcc_jit_param_as_rvalue (param_i),
 136        gcc_jit_param_as_rvalue (param_i));
 137
 138 which is a :c:type:`gcc_jit_rvalue *`, and the various function
 139 parameters: `param_i` and `param_n`, instances of
 140 :c:type:`gcc_jit_param *`, which is a subclass of
 141 :c:type:`gcc_jit_lvalue *` (and, in turn, of :c:type:`gcc_jit_rvalue *`):
 142 we can both read from and write to function parameters within the
 143 body of a function.
 144
 145 Our new example has a couple of local variables.  We create them by
 146 calling :c:func:`gcc_jit_function_new_local`, supplying a type and a
 147 name:
 148
 149 .. code-block:: c
 150
 151   /* Build locals:  */
 152   gcc_jit_lvalue *i =
 153     gcc_jit_function_new_local (func, NULL, the_type, "i");
 154   gcc_jit_lvalue *sum =
 155     gcc_jit_function_new_local (func, NULL, the_type, "sum");
 156
 157 These are instances of :c:type:`gcc_jit_lvalue *` - they can be read from
 158 and written to.
 159
 160 Note that there is no precanned way to create *and* initialize a variable
 161 like in C:
 162
 163 .. code-block:: c
 164
 165    int i = 0;
 166
 167 Instead, having added the local to the function, we have to separately add
 168 an assignment of `0` to `local_i` at the beginning of the function.
 169
 170 Control flow
 171 ************
 172
 173 This function has a loop, so we need to build some basic blocks to
 174 handle the control flow.  In this case, we need 4 blocks:
 175
 176 1. before the loop (initializing the locals)
 177 2. the conditional at the top of the loop (comparing `i < n`)
 178 3. the body of the loop
 179 4. after the loop terminates (`return sum`)
 180
 181 so we create these as :c:type:`gcc_jit_block *` instances within the
 182 :c:type:`gcc_jit_function *`:
 183
 184 .. code-block:: c
 185
 186   gcc_jit_block *b_initial =
 187     gcc_jit_function_new_block (func, "initial");
 188   gcc_jit_block *b_loop_cond =
 189     gcc_jit_function_new_block (func, "loop_cond");
 190   gcc_jit_block *b_loop_body =
 191     gcc_jit_function_new_block (func, "loop_body");
 192   gcc_jit_block *b_after_loop =
 193     gcc_jit_function_new_block (func, "after_loop");
 194
 195 We now populate each block with statements.
 196
 197 The entry block `b_initial` consists of initializations followed by a jump
 198 to the conditional.  We assign `0` to `i` and to `sum`, using
 199 :c:func:`gcc_jit_block_add_assignment` to add
 200 an assignment statement, and using :c:func:`gcc_jit_context_zero` to get
 201 the constant value `0` for the relevant type for the right-hand side of
 202 the assignment:
 203
 204 .. code-block:: c
 205
 206   /* sum = 0; */
 207   gcc_jit_block_add_assignment (
 208     b_initial, NULL,
 209     sum,
 210     gcc_jit_context_zero (ctxt, the_type));
 211
 212   /* i = 0; */
 213   gcc_jit_block_add_assignment (
 214     b_initial, NULL,
 215     i,
 216     gcc_jit_context_zero (ctxt, the_type));
 217
 218 We can then terminate the entry block by jumping to the conditional:
 219
 220 .. code-block:: c
 221
 222   gcc_jit_block_end_with_jump (b_initial, NULL, b_loop_cond);
 223
 224 The conditional block is equivalent to the line `while (i < n)` from our
 225 C example. It contains a single statement: a conditional, which jumps to
 226 one of two destination blocks depending on a boolean
 227 :c:type:`gcc_jit_rvalue *`, in this case the comparison of `i` and `n`.
 228 We build the comparison using :c:func:`gcc_jit_context_new_comparison`:
 229
 230 .. code-block:: c
 231
 232    gcc_jit_rvalue *guard =
 233      gcc_jit_context_new_comparison (
 234        ctxt, NULL,
 235        GCC_JIT_COMPARISON_GE,
 236        gcc_jit_lvalue_as_rvalue (i),
 237        gcc_jit_param_as_rvalue (n));
 238
 239 and can then use this to add `b_loop_cond`'s sole statement, via
 240 :c:func:`gcc_jit_block_end_with_conditional`:
 241
 242 .. code-block:: c
 243
 244   gcc_jit_block_end_with_conditional (b_loop_cond, NULL, guard);
 245
 246 Next, we populate the body of the loop.
 247
 248 The C statement `sum += i * i;` is an assignment operation, where an
 249 lvalue is modified "in-place".  We use
 250 :c:func:`gcc_jit_block_add_assignment_op` to handle these operations:
 251
 252 .. code-block:: c
 253
 254   /* sum += i * i */
 255   gcc_jit_block_add_assignment_op (
 256     b_loop_body, NULL,
 257     sum,
 258     GCC_JIT_BINARY_OP_PLUS,
 259     gcc_jit_context_new_binary_op (
 260       ctxt, NULL,
 261       GCC_JIT_BINARY_OP_MULT, the_type,
 262       gcc_jit_lvalue_as_rvalue (i),
 263       gcc_jit_lvalue_as_rvalue (i)));
 264
 265 The `i++` can be thought of as `i += 1`, and can thus be handled in
 266 a similar way.  We use :c:func:`gcc_jit_context_one` to get the constant
 267 value `1` (for the relevant type) for the right-hand side
 268 of the assignment.
 269
 270 .. code-block:: c
 271
 272   /* i++ */
 273   gcc_jit_block_add_assignment_op (
 274     b_loop_body, NULL,
 275     i,
 276     GCC_JIT_BINARY_OP_PLUS,
 277     gcc_jit_context_one (ctxt, the_type));
 278
 279 .. note::
 280
 281   For numeric constants other than 0 or 1, we could use
 282   :c:func:`gcc_jit_context_new_rvalue_from_int` and
 283   :c:func:`gcc_jit_context_new_rvalue_from_double`.
 284
 285 The loop body completes by jumping back to the conditional:
 286
 287 .. code-block:: c
 288
 289   gcc_jit_block_end_with_jump (b_loop_body, NULL, b_loop_cond);
 290
 291 Finally, we populate the `b_after_loop` block, reached when the loop
 292 conditional is false.  We want to generate the equivalent of:
 293
 294 .. code-block:: c
 295
 296    return sum;
 297
 298 so the block is just one statement:
 299
 300 .. code-block:: c
 301
 302   /* return sum */
 303   gcc_jit_block_end_with_return (
 304     b_after_loop,
 305     NULL,
 306     gcc_jit_lvalue_as_rvalue (sum));
 307
 308 .. note::
 309
 310    You can intermingle block creation with statement creation,
 311    but given that the terminator statements generally include references
 312    to other blocks, I find it's clearer to create all the blocks,
 313    *then* all the statements.
 314
 315 We've finished populating the function.  As before, we can now compile it
 316 to machine code:
 317
 318 .. code-block:: c
 319
 320    gcc_jit_result *result;
 321    result = gcc_jit_context_compile (ctxt);
 322
 323    typedef int (*loop_test_fn_type) (int);
 324    loop_test_fn_type loop_test =
 325     (loop_test_fn_type)gcc_jit_result_get_code (result, "loop_test");
 326    if (!loop_test)
 327      goto error;
 328    printf ("result: %d", loop_test (10));
 329
 330 .. code-block:: bash
 331
 332    result: 285
 333
 334
 335 Visualizing the control flow graph
 336 **********************************
 337
 338 You can see the control flow graph of a function using
 339 :c:func:`gcc_jit_function_dump_to_dot`:
 340
 341 .. code-block:: c
 342
 343   gcc_jit_function_dump_to_dot (func, "/tmp/sum-of-squares.dot");
 344
 345 giving a .dot file in GraphViz format.
 346
 347 You can convert this to an image using `dot`:
 348
 349 .. code-block:: bash
 350
 351    $ dot -Tpng /tmp/sum-of-squares.dot -o /tmp/sum-of-squares.png
 352
 353 or use a viewer (my preferred one is xdot.py; see
 354 https://github.com/jrfonseca/xdot.py; on Fedora you can
 355 install it with `yum install python-xdot`):
 356
 357     .. figure:: sum-of-squares.png
 358       :alt: image of a control flow graph
 359
 360 Full example
 361 ************
 362
 363    .. literalinclude:: ../examples/tut03-sum-of-squares.c
 364     :lines: 1-
 365     :language: c
 366
 367 Building and running it:
 368
 369 .. code-block:: console
 370
 371   $ gcc \
 372       tut03-sum-of-squares.c \
 373       -o tut03-sum-of-squares \
 374       -lgccjit
 375
 376   # Run the built program:
 377   $ ./tut03-sum-of-squares
 378   loop_test returned: 285