Constant fold intrinsics if their arguments are constant. TODO: reference count intri...
[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_VAL(VALUE, NAME, FUNC, STYPE, VTYPE)                    \
36     do {                                                               \
37         (VALUE) = ast_value_new (                                      \
38             parser_ctx(intrin->parser),                                \
39             "__builtin_" NAME,                                         \
40             TYPE_FUNCTION                                              \
41         );                                                             \
42         (VALUE)->intrinsic = true;                                     \
43         (VALUE)->expression.next = (ast_expression*)ast_value_new (    \
44             parser_ctx(intrin->parser),                                \
45             STYPE,                                                     \
46             VTYPE                                                      \
47         );                                                             \
48         (FUNC) = ast_function_new (                                    \
49             parser_ctx(intrin->parser),                                \
50             "__builtin_" NAME,                                         \
51             (VALUE)                                                    \
52         );                                                             \
53     } while (0)
54
55 #define INTRIN_REG(FUNC, VALUE)                                        \
56     do {                                                               \
57         vec_push(intrin->parser->functions, (FUNC));                   \
58         vec_push(intrin->parser->globals,   (ast_expression*)(VALUE)); \
59     } while (0)
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     static ast_value *value = NULL;
79
80     if (!value) {
81         ast_value    *arg1  = ast_value_new(parser_ctx(intrin->parser), "x",     TYPE_FLOAT);
82         ast_value    *arg2  = ast_value_new(parser_ctx(intrin->parser), "y",     TYPE_FLOAT);
83         ast_value    *local = ast_value_new(parser_ctx(intrin->parser), "local", TYPE_FLOAT);
84         ast_block    *body  = ast_block_new(parser_ctx(intrin->parser));
85         ast_block    *l1b   = ast_block_new(parser_ctx(intrin->parser)); /* loop 1 body */
86         ast_block    *l2b   = ast_block_new(parser_ctx(intrin->parser)); /* loop 2 body */
87         ast_loop     *loop1 = NULL;
88         ast_loop     *loop2 = NULL;
89         ast_function *func  = NULL;
90
91         INTRIN_VAL(value, "pow", func, "<float>", TYPE_FLOAT);
92
93         /* arguments */
94         vec_push(value->expression.params, arg1);
95         vec_push(value->expression.params, arg2);
96
97         /* local */
98         vec_push(body->locals, local);
99
100         /* assignment to local of value 1.0f */
101         vec_push(body->exprs,
102             (ast_expression*)ast_store_new (
103                 parser_ctx(intrin->parser),
104                 INSTR_STORE_F,
105                 (ast_expression*)local,
106                 (ast_expression*)intrin->fold->imm_float[1] /* 1 == 1.0f */
107             )
108         );
109
110         /* y >>= 2 */
111         vec_push(l2b->exprs,
112             (ast_expression*)ast_binstore_new (
113                 parser_ctx(intrin->parser),
114                 INSTR_STORE_F,
115                 INSTR_MUL_F,
116                 (ast_expression*)arg2,
117                 (ast_expression*)fold_constgen_float(intrin->parser->fold, 0.25f)
118             )
119         );
120
121         /* x *= x */
122         vec_push(l2b->exprs,
123             (ast_expression*)ast_binstore_new (
124                 parser_ctx(intrin->parser),
125                 INSTR_STORE_F,
126                 INSTR_MUL_F,
127                 (ast_expression*)arg1,
128                 (ast_expression*)arg1
129             )
130         );
131
132         /* while (!(y&1)) */
133         loop2 = ast_loop_new (
134             parser_ctx(intrin->parser),
135             NULL,
136             (ast_expression*)ast_binary_new (
137                 parser_ctx(intrin->parser),
138                 INSTR_AND,
139                 (ast_expression*)arg2,
140                 (ast_expression*)intrin->fold->imm_float[1] /* 1 == 1.0f */
141             ),
142             true, /* ! not */
143             NULL,
144             false,
145             NULL,
146             (ast_expression*)l2b
147         );
148
149         /* push nested loop into loop expressions */
150         vec_push(l1b->exprs, (ast_expression*)loop2);
151
152         /* y-- */
153         vec_push(l1b->exprs,
154             (ast_expression*)ast_binstore_new (
155                 parser_ctx(intrin->parser),
156                 INSTR_STORE_F,
157                 INSTR_SUB_F,
158                 (ast_expression*)arg2,
159                 (ast_expression*)intrin->fold->imm_float[1] /* 1 == 1.0f */
160             )
161         );
162         /* local *= x */
163         vec_push(l1b->exprs,
164             (ast_expression*)ast_binstore_new (
165                 parser_ctx(intrin->parser),
166                 INSTR_STORE_F,
167                 INSTR_MUL_F,
168                 (ast_expression*)local,
169                 (ast_expression*)arg1
170             )
171         );
172
173         /* while (y > 0) */
174         loop1 = ast_loop_new (
175             parser_ctx(intrin->parser),
176             NULL,
177             (ast_expression*)ast_binary_new (
178                 parser_ctx(intrin->parser),
179                 INSTR_GT,
180                 (ast_expression*)arg2,
181                 (ast_expression*)intrin->fold->imm_float[0] /* 0 == 0.0f */
182             ),
183             false,
184             NULL,
185             false,
186             NULL,
187             (ast_expression*)l1b
188         );
189
190         /* push the loop1 into the body for the function */
191         vec_push(body->exprs, (ast_expression*)loop1);
192
193         /* return local; */
194         vec_push(body->exprs,
195             (ast_expression*)ast_return_new (
196                 parser_ctx(intrin->parser),
197                 (ast_expression*)local
198             )
199         );
200
201         /* push block and register intrin for codegen */
202         vec_push(func->blocks, body);
203
204         INTRIN_REG(func, value);
205     }
206
207     return (ast_expression*)value;
208 }
209
210 static ast_expression *intrin_mod(intrin_t *intrin) {
211     /*
212      * float mod(float x, float y) {
213      *   return x - y * floor(x / y);
214      * }
215      */
216     static ast_value *value = NULL;
217
218     if (!value) {
219         ast_call     *call  = ast_call_new (parser_ctx(intrin->parser), intrin_func(intrin, "floor"));
220         ast_value    *arg1  = ast_value_new(parser_ctx(intrin->parser), "x", TYPE_FLOAT);
221         ast_value    *arg2  = ast_value_new(parser_ctx(intrin->parser), "y", TYPE_FLOAT);
222         ast_block    *body  = ast_block_new(parser_ctx(intrin->parser));
223         ast_function *func  = NULL;
224
225         INTRIN_VAL(value, "mod", func, "<float>", TYPE_FLOAT);
226
227         /* floor(x/y) */
228         vec_push(call->params,
229             (ast_expression*)ast_binary_new (
230                 parser_ctx(intrin->parser),
231                 INSTR_DIV_F,
232                 (ast_expression*)arg1,
233                 (ast_expression*)arg2
234             )
235         );
236
237         vec_push(body->exprs,
238             (ast_expression*)ast_return_new(
239                 parser_ctx(intrin->parser),
240                 (ast_expression*)ast_binary_new(
241                     parser_ctx(intrin->parser),
242                     INSTR_SUB_F,
243                     (ast_expression*)arg1,
244                     (ast_expression*)ast_binary_new(
245                         parser_ctx(intrin->parser),
246                         INSTR_MUL_F,
247                         (ast_expression*)arg2,
248                         (ast_expression*)call
249                     )
250                 )
251             )
252         );
253
254         vec_push(value->expression.params, arg1); /* float x (for param) */
255         vec_push(value->expression.params, arg2); /* float y (for param) */
256
257         vec_push(func->blocks,             body); /* {{{ body }}} */
258
259         INTRIN_REG(func, value);
260     }
261
262     return (ast_expression*)value;
263 }
264
265 static ast_expression *intrin_exp(intrin_t *intrin) {
266     /*
267      * float exp(float x) {
268      *     return pow(QC_M_E, x);
269      * }
270      */
271     static ast_value *value = NULL;
272
273     if (!value) {
274         ast_call     *call = ast_call_new (parser_ctx(intrin->parser), intrin_func(intrin, "pow"));
275         ast_value    *arg1 = ast_value_new(parser_ctx(intrin->parser), "x", TYPE_FLOAT);
276         ast_block    *body = ast_block_new(parser_ctx(intrin->parser));
277         ast_function *func = NULL;
278
279         INTRIN_VAL(value, "exp", func, "<float>", TYPE_FLOAT);
280
281         /* push arguments for params to call */
282         vec_push(call->params, (ast_expression*)fold_constgen_float(intrin->fold, QC_M_E));
283         vec_push(call->params, (ast_expression*)arg1);
284
285         /* return pow(QC_M_E, x) */
286         vec_push(body->exprs,
287             (ast_expression*)ast_return_new(
288                 parser_ctx(intrin->parser),
289                 (ast_expression*)call
290             )
291         );
292
293         vec_push(value->expression.params, arg1); /* float x (for param) */
294
295         vec_push(func->blocks,             body); /* {{{ body }}} */
296
297         INTRIN_REG(func, value);
298     }
299
300     return (ast_expression*)value;
301 }
302
303 static ast_expression *intrin_isnan(intrin_t *intrin) {
304     /*
305      * float isnan(float x) {
306      *   float local;
307      *   local = x;
308      *
309      *   return (x != local);
310      * }
311      */
312     static ast_value *value = NULL;
313
314     if (!value) {
315         ast_value    *arg1   = ast_value_new(parser_ctx(intrin->parser), "x",     TYPE_FLOAT);
316         ast_value    *local  = ast_value_new(parser_ctx(intrin->parser), "local", TYPE_FLOAT);
317         ast_block    *body   = ast_block_new(parser_ctx(intrin->parser));
318         ast_function *func   = NULL;
319
320         INTRIN_VAL(value, "isnan", func, "<float>", TYPE_FLOAT);
321
322         vec_push(body->locals, local);
323         vec_push(body->exprs,
324             (ast_expression*)ast_store_new(
325                 parser_ctx(intrin->parser),
326                 INSTR_STORE_F,
327                 (ast_expression*)local,
328                 (ast_expression*)arg1
329             )
330         );
331
332         vec_push(body->exprs,
333             (ast_expression*)ast_return_new(
334                 parser_ctx(intrin->parser),
335                 (ast_expression*)ast_binary_new(
336                     parser_ctx(intrin->parser),
337                     INSTR_NE_F,
338                     (ast_expression*)arg1,
339                     (ast_expression*)local
340                 )
341             )
342         );
343
344         vec_push(value->expression.params, arg1);
345         vec_push(func->blocks, body);
346
347         INTRIN_REG(func, value);
348     }
349
350     return (ast_expression*)value;
351 }
352
353 static ast_expression *intrin_fabs(intrin_t *intrin) {
354     /*
355      * float fabs(float x) {
356      *     return x < 0 ? -x : x;
357      * }
358      */
359     static ast_value *value = NULL;
360     if (!value) {
361         ast_value    *arg1   = ast_value_new(parser_ctx(intrin->parser), "x",     TYPE_FLOAT);
362         ast_block    *body   = ast_block_new(parser_ctx(intrin->parser));
363         ast_function *func   = NULL;
364
365         INTRIN_VAL(value, "fabs", func, "<float>", TYPE_FLOAT);
366
367         vec_push(body->exprs,
368             (ast_expression*)ast_return_new(
369                 parser_ctx(intrin->parser),
370                 (ast_expression*)ast_ternary_new(
371                     parser_ctx(intrin->parser),
372                     (ast_expression*)ast_binary_new(
373                         parser_ctx(intrin->parser),
374                         INSTR_LE,
375                         (ast_expression*)arg1,
376                         (ast_expression*)intrin->fold->imm_float[0]
377                     ),
378                     (ast_expression*)ast_binary_new(
379                         parser_ctx(intrin->parser),
380                         INSTR_SUB_F,
381                         (ast_expression*)intrin->fold->imm_float[0],
382                         (ast_expression*)arg1
383                     ),
384                     (ast_expression*)arg1
385                 )
386             )
387         );
388
389         vec_push(value->expression.params, arg1);
390         vec_push(func->blocks, body);
391
392         INTRIN_REG(func, value);
393     }
394
395     return (ast_expression*)value;
396 }
397
398 #undef INTRIN_REG
399 #undef INTRIN_VAL
400
401 /*
402  * TODO: make static (and handle ast_type_string) here for the builtin
403  * instead of in SYA parse close.
404  */
405 ast_expression *intrin_debug_typestring(intrin_t *intrin) {
406     (void)intrin;
407     return (ast_expression*)0x1;
408 }
409
410 static const intrin_func_t intrinsics[] = {
411     {&intrin_exp,              "__builtin_exp",              "exp"},
412     {&intrin_mod,              "__builtin_mod",              "mod"},
413     {&intrin_pow,              "__builtin_pow",              "pow"},
414     {&intrin_isnan,            "__builtin_isnan",            "isnan"},
415     {&intrin_fabs,             "__builtin_fabs",             "fabs"},
416     {&intrin_debug_typestring, "__builtin_debug_typestring", ""}
417 };
418
419 static void intrin_error(intrin_t *intrin, const char *fmt, ...) {
420     va_list ap;
421     va_start(ap, fmt);
422     vcompile_error(intrin->parser->lex->tok.ctx, fmt, ap);
423     va_end(ap);
424 }
425
426 /* exposed */
427 intrin_t *intrin_init(parser_t *parser) {
428     intrin_t *intrin = (intrin_t*)mem_a(sizeof(intrin_t));
429     intrin->parser     = parser;
430     intrin->fold       = parser->fold;
431     intrin->intrinsics = NULL;
432
433     vec_append(intrin->intrinsics, sizeof(intrinsics)/sizeof(*intrinsics), intrinsics);
434
435     return intrin;
436 }
437
438 void intrin_cleanup(intrin_t *intrin) {
439     vec_free(intrin->intrinsics);
440     mem_d(intrin);
441 }
442
443 ast_expression *intrin_fold(intrin_t *intrin, ast_value *value, ast_expression **exprs) {
444     size_t i;
445
446     if (!value || !value->name)
447         return NULL;
448
449     for (i = 0; i < vec_size(intrin->intrinsics); i++)
450         if (!strcmp(value->name, intrin->intrinsics[i].name))
451             return fold_intrin(intrin->fold, value->name, exprs);
452
453     return NULL;
454 }
455
456 ast_expression *intrin_func(intrin_t *intrin, const char *name) {
457     size_t       i    = 0;
458     void        *find;
459
460     /* try current first */
461     if ((find = (void*)parser_find_global(intrin->parser, name)) && ((ast_value*)find)->expression.vtype == TYPE_FUNCTION)
462         for (i = 0; i < vec_size(intrin->parser->functions); ++i)
463             if (((ast_value*)find)->name && !strcmp(intrin->parser->functions[i]->name, ((ast_value*)find)->name) && intrin->parser->functions[i]->builtin < 0)
464                 return (ast_expression*)find;
465     /* try name second */
466     for (i = 0; i < vec_size(intrin->intrinsics); i++)
467         if (!strcmp(intrin->intrinsics[i].name, name))
468             return intrin->intrinsics[i].intrin(intrin);
469     /* try alias third */
470     for (i = 0; i < vec_size(intrin->intrinsics); i++)
471         if (!strcmp(intrin->intrinsics[i].alias, name))
472             return intrin->intrinsics[i].intrin(intrin);
473
474     intrin_error(intrin, "need function: `%s` compiler depends on it", name);
475     return NULL;
476 }