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