Merge branch 'cooking'
[xonotic/gmqcc.git] / intrin.h
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
24 /*
25  * Provides all the "intrinsics" / "builtins" for GMQCC. These can do
26  * a few things, they can provide fall back implementations for math
27  * functions if the definitions don't exist for some given engine. Or
28  * then can determine definitions for existing builtins, and simply
29  * wrap back to them instead.  This is like a "portable" intrface that
30  * is entered when -fintrin is used (causing all existing builtins to
31  * be ignored by the compiler and instead interface through here.
32  */
33 typedef struct {
34     ast_expression *(*intrin)(parser_t *);
35     const char       *name;
36     const char       *alias;
37 } intrin_t;
38
39 ht intrin_intrinsics() {
40     static ht intrinsics = NULL;
41     if (!intrinsics)
42         intrinsics = util_htnew(PARSER_HT_SIZE);
43
44     return intrinsics;
45 }
46
47 #define INTRIN_VAL(VALUE, NAME, FUNC, STYPE, VTYPE)                   \
48     do {                                                              \
49         (VALUE) = ast_value_new (                                     \
50             parser_ctx(parser),                                       \
51             "__builtin_" NAME,                                        \
52             TYPE_FUNCTION                                             \
53         );                                                            \
54         (VALUE)->expression.next = (ast_expression*)ast_value_new (   \
55             parser_ctx(parser),                                       \
56             STYPE,                                                    \
57             VTYPE                                                     \
58         );                                                            \
59         (FUNC) = ast_function_new (                                   \
60             parser_ctx(parser),                                       \
61             "__builtin_" NAME,                                        \
62             (VALUE)                                                   \
63         );                                                            \
64     } while (0)
65
66 #define INTRIN_REG(FUNC, VALUE)                                       \
67     do {                                                              \
68         vec_push(parser->functions, (FUNC));                          \
69         vec_push(parser->globals,   (ast_expression*)(VALUE));        \
70     } while (0)
71
72
73 ast_expression *intrin_func (parser_t *parser, const char *name);
74
75 #define QC_M_E 2.71828182845905
76
77 ast_expression *intrin_pow(parser_t *parser) {
78     /*
79      * float pow(float x, float y) {
80      *   float local = 1.0f;
81      *   while (y > 0) {
82      *     while (!(y & 1)) {
83      *       y >>= 2;
84      *       x *=  x;
85      *     }
86      *     y--;
87      *     local *= x;
88      *   }
89      *   return local;
90      * } 
91      */
92     static ast_value *value = NULL;
93
94     if (!value) {
95         ast_value    *arg1  = ast_value_new(parser_ctx(parser), "x",     TYPE_FLOAT);
96         ast_value    *arg2  = ast_value_new(parser_ctx(parser), "y",     TYPE_FLOAT);
97         ast_value    *local = ast_value_new(parser_ctx(parser), "local", TYPE_FLOAT);
98         ast_block    *body  = ast_block_new(parser_ctx(parser));
99         ast_block    *l1b   = ast_block_new(parser_ctx(parser)); /* loop 1 body */
100         ast_block    *l2b   = ast_block_new(parser_ctx(parser)); /* looo 2 body */
101         ast_loop     *loop1 = NULL;
102         ast_loop     *loop2 = NULL;
103         ast_function *func  = NULL;
104
105         INTRIN_VAL(value, "pow", func, "<float>", TYPE_FLOAT);
106
107         /* arguments */
108         vec_push(value->expression.params, arg1);
109         vec_push(value->expression.params, arg2);
110
111         /* local */
112         vec_push(body->locals, local);
113
114         /* assignment to local of value 1.0f */
115         vec_push(body->exprs,
116             (ast_expression*)ast_store_new (
117                 parser_ctx(parser),
118                 INSTR_STORE_F,
119                 (ast_expression*)local,
120                 (ast_expression*)parser_const_float_1(parser)
121             )
122         );
123
124         /* y >>= 2 */
125         vec_push(l2b->exprs,
126             (ast_expression*)ast_binstore_new (
127                 parser_ctx(parser),
128                 INSTR_STORE_F,
129                 INSTR_MUL_F,
130                 (ast_expression*)arg2,
131                 (ast_expression*)parser_const_float(parser, 0.25f)
132             )
133         );
134
135         /* x *= x */
136         vec_push(l2b->exprs,
137             (ast_expression*)ast_binstore_new (
138                 parser_ctx(parser),
139                 INSTR_STORE_F,
140                 INSTR_MUL_F,
141                 (ast_expression*)arg1,
142                 (ast_expression*)arg1
143             )
144         );
145
146         /* while (!(y&1)) */
147         loop2 = ast_loop_new (
148             parser_ctx(parser),
149             NULL,
150             (ast_expression*)ast_binary_new (
151                 parser_ctx(parser),
152                 INSTR_AND,
153                 (ast_expression*)arg2,
154                 (ast_expression*)parser_const_float_1(parser)
155             ),
156             true, /* ! not */
157             NULL,
158             false,
159             NULL,
160             (ast_expression*)l2b
161         );
162
163         /* push nested loop into loop expressions */
164         vec_push(l1b->exprs, (ast_expression*)loop2);
165
166         /* y-- */
167         vec_push(l1b->exprs,
168             (ast_expression*)ast_binstore_new (
169                 parser_ctx(parser),
170                 INSTR_STORE_F,
171                 INSTR_SUB_F,
172                 (ast_expression*)arg2,
173                 (ast_expression*)parser_const_float_1(parser)
174             )
175         );
176         /* local *= x */
177         vec_push(l1b->exprs,
178             (ast_expression*)ast_binstore_new (
179                 parser_ctx(parser),
180                 INSTR_STORE_F,
181                 INSTR_MUL_F,
182                 (ast_expression*)local,
183                 (ast_expression*)arg1
184             )
185         );
186
187         /* while (y > 0) */
188         loop1 = ast_loop_new (
189             parser_ctx(parser),
190             NULL,
191             (ast_expression*)ast_binary_new (
192                 parser_ctx(parser),
193                 INSTR_GT,
194                 (ast_expression*)arg2,
195                 (ast_expression*)parser_const_float_0(parser)
196             ),
197             false,
198             NULL,
199             false,
200             NULL,
201             (ast_expression*)l1b
202         );
203
204         /* push the loop1 into the body for the function */
205         vec_push(body->exprs, (ast_expression*)loop1);
206
207         /* return local; */
208         vec_push(body->exprs,
209             (ast_expression*)ast_return_new (
210                 parser_ctx(parser),
211                 (ast_expression*)local
212             )
213         );
214
215         /* push block and register intrin for codegen */
216         vec_push(func->blocks, body);
217
218         INTRIN_REG(func, value);
219     }
220
221     return (ast_expression*)value;
222 }
223
224 ast_expression *intrin_mod(parser_t *parser) {
225     /*
226      * float mod(float x, float y) {
227      *   return x - y * floor(x / y);
228      * }
229      */    
230     static ast_value *value = NULL;
231
232     if (!value) {
233         ast_call     *call  = ast_call_new (parser_ctx(parser), intrin_func(parser, "floor"));
234         ast_value    *arg1  = ast_value_new(parser_ctx(parser), "x", TYPE_FLOAT);
235         ast_value    *arg2  = ast_value_new(parser_ctx(parser), "y", TYPE_FLOAT);
236         ast_block    *body  = ast_block_new(parser_ctx(parser));
237         ast_function *func  = NULL;
238
239         INTRIN_VAL(value, "mod", func, "<float>", TYPE_FLOAT);
240
241         /* floor(x/y) */
242         vec_push(call->params,
243             (ast_expression*)ast_binary_new (
244                 parser_ctx(parser),
245                 INSTR_DIV_F,
246                 (ast_expression*)arg1,
247                 (ast_expression*)arg2
248             )
249         );
250
251         vec_push(body->exprs,
252             (ast_expression*)ast_return_new(
253                 parser_ctx(parser),
254                 (ast_expression*)ast_binary_new(
255                     parser_ctx(parser),
256                     INSTR_SUB_F,
257                     (ast_expression*)arg1,
258                     (ast_expression*)ast_binary_new(
259                         parser_ctx(parser),
260                         INSTR_MUL_F,
261                         (ast_expression*)arg2,
262                         (ast_expression*)call
263                     )
264                 )
265             )
266         );
267
268         vec_push(value->expression.params, arg1); /* float x (for param) */
269         vec_push(value->expression.params, arg2); /* float y (for param) */
270
271         vec_push(func->blocks,            body); /* {{{ body }}} */
272
273         INTRIN_REG(func, value);
274     }
275
276     return (ast_expression*)value;
277 }
278
279 ast_expression *intrin_exp(parser_t *parser) {
280     /*
281      * float exp(float x) {
282      *     return pow(QC_M_E, x);
283      * }
284      */
285     static ast_value *value = NULL;
286
287     if (!value) {
288         ast_call     *call = ast_call_new    (parser_ctx(parser), intrin_func(parser, "pow"));
289         ast_value    *arg1 = ast_value_new   (parser_ctx(parser), "x", TYPE_FLOAT);
290         ast_block    *body = ast_block_new   (parser_ctx(parser));
291         ast_function *func = NULL;
292
293         INTRIN_VAL(value, "exp", func, "<float>", TYPE_FLOAT);
294
295         /* push arguments for params to call */
296         vec_push(call->params, (ast_expression*)parser_const_float(parser, QC_M_E));
297         vec_push(call->params, (ast_expression*)arg1);
298
299         /* return pow(QC_M_E, x) */
300         vec_push(body->exprs,
301             (ast_expression*)ast_return_new(
302                 parser_ctx(parser),
303                 (ast_expression*)call
304             )
305         );
306
307         vec_push(value->expression.params, arg1); /* float x (for param) */
308
309         vec_push(func->blocks,             body); /* {{{ body }}} */
310
311         INTRIN_REG(func, value);
312     }
313
314     return (ast_expression*)value;
315 }
316
317 ast_expression *intrin_isnan(parser_t *parser) {
318     /*
319      * float isnan(float x) {
320      *   float local;
321      *   local = x;
322      *
323      *   return (x != local);
324      * } 
325      */      
326     static ast_value *value = NULL;
327
328     if (!value) {
329         ast_value    *arg1   = ast_value_new (parser_ctx(parser), "x", TYPE_FLOAT);
330         ast_value    *local  = ast_value_new (parser_ctx(parser), "local", TYPE_FLOAT);
331         ast_block    *body   = ast_block_new (parser_ctx(parser));
332         ast_function *func   = NULL;
333     
334         INTRIN_VAL(value, "isnan", func, "<float>", TYPE_FLOAT);
335
336         vec_push(body->locals, local);
337         vec_push(body->exprs,
338             (ast_expression*)ast_store_new(
339                 parser_ctx(parser),
340                 INSTR_STORE_F,
341                 (ast_expression*)local,
342                 (ast_expression*)arg1
343             )
344         );
345
346         vec_push(body->exprs,
347             (ast_expression*)ast_return_new(
348                 parser_ctx(parser),
349                 (ast_expression*)ast_binary_new(
350                     parser_ctx(parser),
351                     INSTR_NE_F,
352                     (ast_expression*)arg1,
353                     (ast_expression*)local
354                 )
355             )
356         );
357
358         vec_push(value->expression.params, arg1);
359
360         vec_push(func->blocks, body);
361
362         INTRIN_REG(func, value);
363     }
364
365     return (ast_expression*)value;
366 }
367
368 static intrin_t intrinsics[] = {
369     {&intrin_exp,   "__builtin_exp",   "exp"},
370     {&intrin_mod,   "__builtin_mod",   "mod"},
371     {&intrin_pow,   "__builtin_pow",   "pow"},
372     {&intrin_isnan, "__builtin_isnan", "isnan"}
373 };
374
375 void intrin_intrinsics_destroy(parser_t *parser) {
376     /*size_t i;*/
377     (void)parser;
378     util_htdel(intrin_intrinsics());
379 #if 0
380     for (i = 0; i < sizeof(intrinsics)/sizeof(intrin_t); i++)
381         ast_value_delete( (ast_value*) intrinsics[i].intrin(parser));
382 #endif
383 }
384
385
386 ast_expression *intrin_func(parser_t *parser, const char *name) {
387     static bool  init = false;
388     size_t       i    = 0;
389     void        *find;
390
391     /* register the intrinsics in the hashtable for O(1) lookup */
392     if (!init) {
393         for (i = 0; i < sizeof(intrinsics)/sizeof(*intrinsics); i++)
394             util_htset(intrin_intrinsics(), intrinsics[i].alias, &intrinsics[i]);
395
396         init = true; /* only once */
397     }
398
399     /*
400      * jesus fucking christ, Blub design something less fucking
401      * impossible to use, like a ast_is_builtin(ast_expression *), also
402      * use a hashtable :P 
403      */  
404     if ((find = (void*)parser_find_global(parser, name)) && ((ast_value*)find)->expression.vtype == TYPE_FUNCTION)
405         for (i = 0; i < vec_size(parser->functions); ++i)
406             if (((ast_value*)find)->name && !strcmp(parser->functions[i]->name, ((ast_value*)find)->name) && parser->functions[i]->builtin < 0)
407                 return find;
408
409     if ((find = util_htget(intrin_intrinsics(), name))) {
410         /* intrinsic is in table. This will "generate the function" so
411          * to speak (if it's not already generated).
412          */  
413         return ((intrin_t*)find)->intrin(parser);
414     }
415
416     parseerror(parser, "need function: `%s` compiler depends on it", name);
417     return NULL;
418 }