Fix handling on intrinsic folding, this closes #118.
[xonotic/gmqcc.git] / intrin.c
1 /*
2  * Copyright (C) 2012, 2013
3  *     Dale Weiler
4  *
5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
6  * this software and associated documentation files (the "Software"), to deal in
7  * the Software without restriction, including without limitation the rights to
8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
9  * of the Software, and to permit persons to whom the Software is furnished to do
10  * so, subject to the following conditions:
11  *
12  * The above copyright notice and this permission notice shall be included in all
13  * copies or substantial portions of the Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21  * SOFTWARE.
22  */
23 #include <string.h>
24 #include "parser.h"
25
26 /*
27  * Provides all the "intrinsics" / "builtins" for GMQCC. These can do
28  * a few things, they can provide fall back implementations for math
29  * functions if the definitions don't exist for some given engine. Or
30  * then can determine definitions for existing builtins, and simply
31  * wrap back to them instead.  This is like a "portable" intrface that
32  * is entered when -fintrin is used (causing all existing builtins to
33  * be ignored by the compiler and instead interface through here.
34  */
35 #define intrin_ctx(I) parser_ctx((I)->parser)
36
37 static GMQCC_INLINE ast_function *intrin_value(intrin_t *intrin, ast_value **out, const char *name, qcint_t vtype) {
38     ast_value    *value = NULL;
39     ast_function *func  = NULL;
40     char          buffer[1024];
41     char          stype [1024];
42
43     util_snprintf(buffer, sizeof(buffer), "__builtin_%s", name);
44     util_snprintf(stype,  sizeof(stype),   "<%s>",        type_name[vtype]);
45
46     value                    = ast_value_new(intrin_ctx(intrin), buffer, TYPE_FUNCTION);
47     value->intrinsic         = true;
48     value->expression.next   = (ast_expression*)ast_value_new(intrin_ctx(intrin), stype, vtype);
49     func                     = ast_function_new(intrin_ctx(intrin), buffer, value);
50     value->expression.flags |= AST_FLAG_ERASEABLE;
51
52     *out = value;
53     return func;
54 }
55
56 static GMQCC_INLINE void intrin_reg(intrin_t *intrin, ast_value *const value, ast_function *const func) {
57     vec_push(intrin->parser->functions, func);
58     vec_push(intrin->parser->globals,   (ast_expression*)value);
59 }
60
61 #define QC_M_E 2.71828182845905f
62
63 static ast_expression *intrin_pow (intrin_t *intrin) {
64     /*
65      * float pow(float x, float y) {
66      *   float local = 1.0f;
67      *   while (y > 0) {
68      *     while (!(y & 1)) {
69      *       y >>= 2;
70      *       x *=  x;
71      *     }
72      *     y--;
73      *     local *= x;
74      *   }
75      *   return local;
76      * }
77      */
78     ast_value    *value = NULL;
79     ast_value    *arg1  = ast_value_new(intrin_ctx(intrin), "x",     TYPE_FLOAT);
80     ast_value    *arg2  = ast_value_new(intrin_ctx(intrin), "y",     TYPE_FLOAT);
81     ast_value    *local = ast_value_new(intrin_ctx(intrin), "local", TYPE_FLOAT);
82     ast_block    *body  = ast_block_new(intrin_ctx(intrin));
83     ast_block    *l1b   = ast_block_new(intrin_ctx(intrin)); /* loop 1 body */
84     ast_block    *l2b   = ast_block_new(intrin_ctx(intrin)); /* loop 2 body */
85     ast_loop     *loop1 = NULL;
86     ast_loop     *loop2 = NULL;
87     ast_function *func  = intrin_value(intrin, &value, "pow", TYPE_FLOAT);
88
89     /* arguments */
90     vec_push(value->expression.params, arg1);
91     vec_push(value->expression.params, arg2);
92
93     /* local */
94     vec_push(body->locals, local);
95
96     /* assignment to local of value 1.0f */
97     vec_push(body->exprs,
98         (ast_expression*)ast_store_new (
99             intrin_ctx(intrin),
100             INSTR_STORE_F,
101             (ast_expression*)local,
102             (ast_expression*)intrin->fold->imm_float[1] /* 1 == 1.0f */
103         )
104     );
105
106     /* y >>= 2 */
107     vec_push(l2b->exprs,
108         (ast_expression*)ast_binstore_new (
109             intrin_ctx(intrin),
110             INSTR_STORE_F,
111             INSTR_MUL_F,
112             (ast_expression*)arg2,
113             (ast_expression*)fold_constgen_float(intrin->parser->fold, 0.25f)
114         )
115     );
116
117     /* x *= x */
118     vec_push(l2b->exprs,
119         (ast_expression*)ast_binstore_new (
120             intrin_ctx(intrin),
121             INSTR_STORE_F,
122             INSTR_MUL_F,
123             (ast_expression*)arg1,
124             (ast_expression*)arg1
125         )
126     );
127
128     /* while (!(y&1)) */
129     loop2 = ast_loop_new (
130         intrin_ctx(intrin),
131         NULL,
132         (ast_expression*)ast_binary_new (
133             intrin_ctx(intrin),
134             INSTR_AND,
135             (ast_expression*)arg2,
136             (ast_expression*)intrin->fold->imm_float[1] /* 1 == 1.0f */
137         ),
138         true, /* ! not */
139         NULL,
140         false,
141         NULL,
142         (ast_expression*)l2b
143     );
144
145     /* push nested loop into loop expressions */
146     vec_push(l1b->exprs, (ast_expression*)loop2);
147
148     /* y-- */
149     vec_push(l1b->exprs,
150         (ast_expression*)ast_binstore_new (
151             intrin_ctx(intrin),
152             INSTR_STORE_F,
153             INSTR_SUB_F,
154             (ast_expression*)arg2,
155             (ast_expression*)intrin->fold->imm_float[1] /* 1 == 1.0f */
156         )
157     );
158     /* local *= x */
159     vec_push(l1b->exprs,
160         (ast_expression*)ast_binstore_new (
161             intrin_ctx(intrin),
162             INSTR_STORE_F,
163             INSTR_MUL_F,
164             (ast_expression*)local,
165             (ast_expression*)arg1
166         )
167     );
168
169     /* while (y > 0) */
170     loop1 = ast_loop_new (
171         intrin_ctx(intrin),
172         NULL,
173         (ast_expression*)ast_binary_new (
174             intrin_ctx(intrin),
175             INSTR_GT,
176             (ast_expression*)arg2,
177             (ast_expression*)intrin->fold->imm_float[0] /* 0 == 0.0f */
178         ),
179         false,
180         NULL,
181         false,
182         NULL,
183         (ast_expression*)l1b
184     );
185
186     /* push the loop1 into the body for the function */
187     vec_push(body->exprs, (ast_expression*)loop1);
188
189     /* return local; */
190     vec_push(body->exprs,
191         (ast_expression*)ast_return_new (
192             intrin_ctx(intrin),
193             (ast_expression*)local
194         )
195     );
196
197     /* push block and register intrin for codegen */
198     vec_push(func->blocks, body);
199
200     intrin_reg(intrin, value, func);
201
202     return (ast_expression*)value;
203 }
204
205 static ast_expression *intrin_mod(intrin_t *intrin) {
206     /*
207      * float mod(float x, float y) {
208      *   return x - y * floor(x / y);
209      * }
210      */
211     ast_value    *value = NULL;
212     ast_call     *call  = ast_call_new (intrin_ctx(intrin), intrin_func(intrin, "floor"));
213     ast_value    *arg1  = ast_value_new(intrin_ctx(intrin), "x", TYPE_FLOAT);
214     ast_value    *arg2  = ast_value_new(intrin_ctx(intrin), "y", TYPE_FLOAT);
215     ast_block    *body  = ast_block_new(intrin_ctx(intrin));
216     ast_function *func  = intrin_value(intrin, &value, "mod", TYPE_FLOAT);
217
218     /* floor(x/y) */
219     vec_push(call->params,
220         (ast_expression*)ast_binary_new (
221             intrin_ctx(intrin),
222             INSTR_DIV_F,
223             (ast_expression*)arg1,
224             (ast_expression*)arg2
225         )
226     );
227
228     vec_push(body->exprs,
229         (ast_expression*)ast_return_new(
230             intrin_ctx(intrin),
231             (ast_expression*)ast_binary_new(
232                 intrin_ctx(intrin),
233                 INSTR_SUB_F,
234                 (ast_expression*)arg1,
235                 (ast_expression*)ast_binary_new(
236                     intrin_ctx(intrin),
237                     INSTR_MUL_F,
238                     (ast_expression*)arg2,
239                     (ast_expression*)call
240                 )
241             )
242         )
243     );
244
245     vec_push(value->expression.params, arg1); /* float x (for param) */
246     vec_push(value->expression.params, arg2); /* float y (for param) */
247
248     vec_push(func->blocks,             body); /* {{{ body }}} */
249
250     intrin_reg(intrin, value, func);
251
252     return (ast_expression*)value;
253 }
254
255 static ast_expression *intrin_exp(intrin_t *intrin) {
256     /*
257      * float exp(float x) {
258      *     return pow(QC_M_E, x);
259      * }
260      */
261     ast_value    *value = NULL;
262     ast_call     *call  = ast_call_new (intrin_ctx(intrin), intrin_func(intrin, "pow"));
263     ast_value    *arg1  = ast_value_new(intrin_ctx(intrin), "x", TYPE_FLOAT);
264     ast_block    *body  = ast_block_new(intrin_ctx(intrin));
265     ast_function *func  = intrin_value(intrin, &value, "exp", TYPE_FLOAT);
266
267     /* push arguments for params to call */
268     vec_push(call->params, (ast_expression*)fold_constgen_float(intrin->fold, QC_M_E));
269     vec_push(call->params, (ast_expression*)arg1);
270
271     /* return pow(QC_M_E, x) */
272     vec_push(body->exprs,
273         (ast_expression*)ast_return_new(
274             intrin_ctx(intrin),
275             (ast_expression*)call
276         )
277     );
278
279     vec_push(value->expression.params, arg1); /* float x (for param) */
280
281     vec_push(func->blocks,             body); /* {{{ body }}} */
282
283     intrin_reg(intrin, value, func);
284
285     return (ast_expression*)value;
286 }
287
288 static ast_expression *intrin_isnan(intrin_t *intrin) {
289     /*
290      * float isnan(float x) {
291      *   float local;
292      *   local = x;
293      *
294      *   return (x != local);
295      * }
296      */
297     ast_value    *value  = NULL;
298     ast_value    *arg1   = ast_value_new(intrin_ctx(intrin), "x",     TYPE_FLOAT);
299     ast_value    *local  = ast_value_new(intrin_ctx(intrin), "local", TYPE_FLOAT);
300     ast_block    *body   = ast_block_new(intrin_ctx(intrin));
301     ast_function *func   = intrin_value(intrin, &value, "isnan", TYPE_FLOAT);
302
303     vec_push(body->locals, local);
304     vec_push(body->exprs,
305         (ast_expression*)ast_store_new(
306             intrin_ctx(intrin),
307             INSTR_STORE_F,
308             (ast_expression*)local,
309             (ast_expression*)arg1
310         )
311     );
312
313     vec_push(body->exprs,
314         (ast_expression*)ast_return_new(
315             intrin_ctx(intrin),
316             (ast_expression*)ast_binary_new(
317                 intrin_ctx(intrin),
318                 INSTR_NE_F,
319                 (ast_expression*)arg1,
320                 (ast_expression*)local
321             )
322         )
323     );
324
325     vec_push(value->expression.params, arg1);
326     vec_push(func->blocks, body);
327
328     intrin_reg(intrin, value, func);
329
330     return (ast_expression*)value;
331 }
332
333 static ast_expression *intrin_fabs(intrin_t *intrin) {
334     /*
335      * float fabs(float x) {
336      *     return x < 0 ? -x : x;
337      * }
338      */
339     ast_value    *value  = NULL;
340     ast_value    *arg1   = ast_value_new(intrin_ctx(intrin), "x", TYPE_FLOAT);
341     ast_block    *body   = ast_block_new(intrin_ctx(intrin));
342     ast_function *func   = intrin_value(intrin, &value, "fabs", TYPE_FLOAT);
343
344     vec_push(body->exprs,
345         (ast_expression*)ast_return_new(
346             intrin_ctx(intrin),
347             (ast_expression*)ast_ternary_new(
348                 intrin_ctx(intrin),
349                 (ast_expression*)ast_binary_new(
350                     intrin_ctx(intrin),
351                     INSTR_LE,
352                     (ast_expression*)arg1,
353                     (ast_expression*)intrin->fold->imm_float[0]
354                 ),
355                 (ast_expression*)ast_binary_new(
356                     intrin_ctx(intrin),
357                     INSTR_SUB_F,
358                     (ast_expression*)intrin->fold->imm_float[0],
359                     (ast_expression*)arg1
360                 ),
361                 (ast_expression*)arg1
362             )
363         )
364     );
365
366     vec_push(value->expression.params, arg1);
367     vec_push(func->blocks, body);
368
369     intrin_reg(intrin, value, func);
370
371     return (ast_expression*)value;
372 }
373
374 /*
375  * TODO: make static (and handle ast_type_string) here for the builtin
376  * instead of in SYA parse close.
377  */
378 ast_expression *intrin_debug_typestring(intrin_t *intrin) {
379     (void)intrin;
380     return (ast_expression*)0x1;
381 }
382
383 static const intrin_func_t intrinsics[] = {
384     {&intrin_exp,              "__builtin_exp",              "exp",   1},
385     {&intrin_mod,              "__builtin_mod",              "mod",   2},
386     {&intrin_pow,              "__builtin_pow",              "pow",   2},
387     {&intrin_isnan,            "__builtin_isnan",            "isnan", 1},
388     {&intrin_fabs,             "__builtin_fabs",             "fabs",  1},
389     {&intrin_debug_typestring, "__builtin_debug_typestring", "",      0}
390 };
391
392 static void intrin_error(intrin_t *intrin, const char *fmt, ...) {
393     va_list ap;
394     va_start(ap, fmt);
395     vcompile_error(intrin->parser->lex->tok.ctx, fmt, ap);
396     va_end(ap);
397 }
398
399 /* exposed */
400 intrin_t *intrin_init(parser_t *parser) {
401     intrin_t *intrin = (intrin_t*)mem_a(sizeof(intrin_t));
402     size_t    i;
403
404     intrin->parser     = parser;
405     intrin->fold       = parser->fold;
406     intrin->intrinsics = NULL;
407     intrin->generated  = NULL;
408
409     vec_append(intrin->intrinsics, GMQCC_ARRAY_COUNT(intrinsics), intrinsics);
410
411     /* populate with null pointers for tracking generation */
412     for (i = 0; i < GMQCC_ARRAY_COUNT(intrinsics); i++)
413         vec_push(intrin->generated, NULL);
414
415     return intrin;
416 }
417
418 void intrin_cleanup(intrin_t *intrin) {
419     vec_free(intrin->intrinsics);
420     vec_free(intrin->generated);
421     mem_d(intrin);
422 }
423
424 ast_expression *intrin_fold(intrin_t *intrin, ast_value *value, ast_expression **exprs) {
425     size_t i;
426     if (!value || !value->name)
427         return NULL;
428     for (i = 0; i < vec_size(intrin->intrinsics); i++)
429         if (!strcmp(value->name, intrin->intrinsics[i].name))
430             return (vec_size(exprs) != intrin->intrinsics[i].args)
431                         ? NULL
432                         : fold_intrin(intrin->fold, value->name + 10, exprs);
433     return NULL;
434 }
435
436 static GMQCC_INLINE ast_expression *intrin_func_try(intrin_t *intrin, size_t offset, const char *compare) {
437     size_t i;
438     for (i = 0; i < vec_size(intrin->intrinsics); i++) {
439         if (strcmp(*(char **)((char *)&intrin->intrinsics[i] + offset), compare))
440             continue;
441         if (intrin->generated[i])
442             return intrin->generated[i];
443         return intrin->generated[i] = intrin->intrinsics[i].intrin(intrin);
444     }
445     return NULL;
446 }
447
448 ast_expression *intrin_func(intrin_t *intrin, const char *name) {
449     size_t           i;
450     ast_expression  *find;
451
452     /* try current first */
453     if ((find = parser_find_global(intrin->parser, name)) && ((ast_value*)find)->expression.vtype == TYPE_FUNCTION)
454         for (i = 0; i < vec_size(intrin->parser->functions); ++i)
455             if (((ast_value*)find)->name && !strcmp(intrin->parser->functions[i]->name, ((ast_value*)find)->name) && intrin->parser->functions[i]->builtin < 0)
456                 return find;
457     /* try name second */
458     if ((find = intrin_func_try(intrin, offsetof(intrin_func_t, name),  name)))
459         return find;
460     /* try alias third */
461     if ((find = intrin_func_try(intrin, offsetof(intrin_func_t, alias), name)))
462         return find;
463
464     intrin_error(intrin, "need function: `%s` compiler depends on it", name);
465     return NULL;
466 }