Fix
[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 static ht intrin_intrinsics(void) {
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 #define QC_M_E 2.71828182845905
73
74 static ast_expression *intrin_func(parser_t *parser, const char *name);
75 static ast_expression *intrin_pow (parser_t *parser) {
76     /*
77      * float pow(float x, float y) {
78      *   float local = 1.0f;
79      *   while (y > 0) {
80      *     while (!(y & 1)) {
81      *       y >>= 2;
82      *       x *=  x;
83      *     }
84      *     y--;
85      *     local *= x;
86      *   }
87      *   return local;
88      * }
89      */
90     static ast_value *value = NULL;
91
92     if (!value) {
93         ast_value    *arg1  = ast_value_new(parser_ctx(parser), "x",     TYPE_FLOAT);
94         ast_value    *arg2  = ast_value_new(parser_ctx(parser), "y",     TYPE_FLOAT);
95         ast_value    *local = ast_value_new(parser_ctx(parser), "local", TYPE_FLOAT);
96         ast_block    *body  = ast_block_new(parser_ctx(parser));
97         ast_block    *l1b   = ast_block_new(parser_ctx(parser)); /* loop 1 body */
98         ast_block    *l2b   = ast_block_new(parser_ctx(parser)); /* looo 2 body */
99         ast_loop     *loop1 = NULL;
100         ast_loop     *loop2 = NULL;
101         ast_function *func  = NULL;
102
103         INTRIN_VAL(value, "pow", func, "<float>", TYPE_FLOAT);
104
105         /* arguments */
106         vec_push(value->expression.params, arg1);
107         vec_push(value->expression.params, arg2);
108
109         /* local */
110         vec_push(body->locals, local);
111
112         /* assignment to local of value 1.0f */
113         vec_push(body->exprs,
114             (ast_expression*)ast_store_new (
115                 parser_ctx(parser),
116                 INSTR_STORE_F,
117                 (ast_expression*)local,
118                 (ast_expression*)parser->fold->imm_float[1] /* 1 == 1.0f */
119             )
120         );
121
122         /* y >>= 2 */
123         vec_push(l2b->exprs,
124             (ast_expression*)ast_binstore_new (
125                 parser_ctx(parser),
126                 INSTR_STORE_F,
127                 INSTR_MUL_F,
128                 (ast_expression*)arg2,
129                 (ast_expression*)fold_constgen_float(parser->fold, 0.25f)
130             )
131         );
132
133         /* x *= x */
134         vec_push(l2b->exprs,
135             (ast_expression*)ast_binstore_new (
136                 parser_ctx(parser),
137                 INSTR_STORE_F,
138                 INSTR_MUL_F,
139                 (ast_expression*)arg1,
140                 (ast_expression*)arg1
141             )
142         );
143
144         /* while (!(y&1)) */
145         loop2 = ast_loop_new (
146             parser_ctx(parser),
147             NULL,
148             (ast_expression*)ast_binary_new (
149                 parser_ctx(parser),
150                 INSTR_AND,
151                 (ast_expression*)arg2,
152                 (ast_expression*)parser->fold->imm_float[1] /* 1 == 1.0f */
153             ),
154             true, /* ! not */
155             NULL,
156             false,
157             NULL,
158             (ast_expression*)l2b
159         );
160
161         /* push nested loop into loop expressions */
162         vec_push(l1b->exprs, (ast_expression*)loop2);
163
164         /* y-- */
165         vec_push(l1b->exprs,
166             (ast_expression*)ast_binstore_new (
167                 parser_ctx(parser),
168                 INSTR_STORE_F,
169                 INSTR_SUB_F,
170                 (ast_expression*)arg2,
171                 (ast_expression*)parser->fold->imm_float[1] /* 1 == 1.0f */
172             )
173         );
174         /* local *= x */
175         vec_push(l1b->exprs,
176             (ast_expression*)ast_binstore_new (
177                 parser_ctx(parser),
178                 INSTR_STORE_F,
179                 INSTR_MUL_F,
180                 (ast_expression*)local,
181                 (ast_expression*)arg1
182             )
183         );
184
185         /* while (y > 0) */
186         loop1 = ast_loop_new (
187             parser_ctx(parser),
188             NULL,
189             (ast_expression*)ast_binary_new (
190                 parser_ctx(parser),
191                 INSTR_GT,
192                 (ast_expression*)arg2,
193                 (ast_expression*)parser->fold->imm_float[0] /* 0 == 0.0f */
194             ),
195             false,
196             NULL,
197             false,
198             NULL,
199             (ast_expression*)l1b
200         );
201
202         /* push the loop1 into the body for the function */
203         vec_push(body->exprs, (ast_expression*)loop1);
204
205         /* return local; */
206         vec_push(body->exprs,
207             (ast_expression*)ast_return_new (
208                 parser_ctx(parser),
209                 (ast_expression*)local
210             )
211         );
212
213         /* push block and register intrin for codegen */
214         vec_push(func->blocks, body);
215
216         INTRIN_REG(func, value);
217     }
218
219     return (ast_expression*)value;
220 }
221
222 static ast_expression *intrin_mod(parser_t *parser) {
223     /*
224      * float mod(float x, float y) {
225      *   return x - y * floor(x / y);
226      * }
227      */
228     static ast_value *value = NULL;
229
230     if (!value) {
231         ast_call     *call  = ast_call_new (parser_ctx(parser), intrin_func(parser, "floor"));
232         ast_value    *arg1  = ast_value_new(parser_ctx(parser), "x", TYPE_FLOAT);
233         ast_value    *arg2  = ast_value_new(parser_ctx(parser), "y", TYPE_FLOAT);
234         ast_block    *body  = ast_block_new(parser_ctx(parser));
235         ast_function *func  = NULL;
236
237         INTRIN_VAL(value, "mod", func, "<float>", TYPE_FLOAT);
238
239         /* floor(x/y) */
240         vec_push(call->params,
241             (ast_expression*)ast_binary_new (
242                 parser_ctx(parser),
243                 INSTR_DIV_F,
244                 (ast_expression*)arg1,
245                 (ast_expression*)arg2
246             )
247         );
248
249         vec_push(body->exprs,
250             (ast_expression*)ast_return_new(
251                 parser_ctx(parser),
252                 (ast_expression*)ast_binary_new(
253                     parser_ctx(parser),
254                     INSTR_SUB_F,
255                     (ast_expression*)arg1,
256                     (ast_expression*)ast_binary_new(
257                         parser_ctx(parser),
258                         INSTR_MUL_F,
259                         (ast_expression*)arg2,
260                         (ast_expression*)call
261                     )
262                 )
263             )
264         );
265
266         vec_push(value->expression.params, arg1); /* float x (for param) */
267         vec_push(value->expression.params, arg2); /* float y (for param) */
268
269         vec_push(func->blocks,            body); /* {{{ body }}} */
270
271         INTRIN_REG(func, value);
272     }
273
274     return (ast_expression*)value;
275 }
276
277 static ast_expression *intrin_exp(parser_t *parser) {
278     /*
279      * float exp(float x) {
280      *     return pow(QC_M_E, x);
281      * }
282      */
283     static ast_value *value = NULL;
284
285     if (!value) {
286         ast_call     *call = ast_call_new    (parser_ctx(parser), intrin_func(parser, "pow"));
287         ast_value    *arg1 = ast_value_new   (parser_ctx(parser), "x", TYPE_FLOAT);
288         ast_block    *body = ast_block_new   (parser_ctx(parser));
289         ast_function *func = NULL;
290
291         INTRIN_VAL(value, "exp", func, "<float>", TYPE_FLOAT);
292
293         /* push arguments for params to call */
294         vec_push(call->params, (ast_expression*)fold_constgen_float(parser->fold, QC_M_E));
295         vec_push(call->params, (ast_expression*)arg1);
296
297         /* return pow(QC_M_E, x) */
298         vec_push(body->exprs,
299             (ast_expression*)ast_return_new(
300                 parser_ctx(parser),
301                 (ast_expression*)call
302             )
303         );
304
305         vec_push(value->expression.params, arg1); /* float x (for param) */
306
307         vec_push(func->blocks,             body); /* {{{ body }}} */
308
309         INTRIN_REG(func, value);
310     }
311
312     return (ast_expression*)value;
313 }
314
315 static ast_expression *intrin_isnan(parser_t *parser) {
316     /*
317      * float isnan(float x) {
318      *   float local;
319      *   local = x;
320      *
321      *   return (x != local);
322      * }
323      */
324     static ast_value *value = NULL;
325
326     if (!value) {
327         ast_value    *arg1   = ast_value_new (parser_ctx(parser), "x",     TYPE_FLOAT);
328         ast_value    *local  = ast_value_new (parser_ctx(parser), "local", TYPE_FLOAT);
329         ast_block    *body   = ast_block_new (parser_ctx(parser));
330         ast_function *func   = NULL;
331
332         INTRIN_VAL(value, "isnan", func, "<float>", TYPE_FLOAT);
333
334         vec_push(body->locals, local);
335         vec_push(body->exprs,
336             (ast_expression*)ast_store_new(
337                 parser_ctx(parser),
338                 INSTR_STORE_F,
339                 (ast_expression*)local,
340                 (ast_expression*)arg1
341             )
342         );
343
344         vec_push(body->exprs,
345             (ast_expression*)ast_return_new(
346                 parser_ctx(parser),
347                 (ast_expression*)ast_binary_new(
348                     parser_ctx(parser),
349                     INSTR_NE_F,
350                     (ast_expression*)arg1,
351                     (ast_expression*)local
352                 )
353             )
354         );
355
356         vec_push(value->expression.params, arg1);
357
358         vec_push(func->blocks, body);
359
360         INTRIN_REG(func, value);
361     }
362
363     return (ast_expression*)value;
364 }
365
366 static ast_expression *intrin_debug_typestring(parser_t *parser) {
367     (void)parser;
368     return (ast_expression*)0x1;
369 }
370
371 static intrin_t intrinsics[] = {
372     {&intrin_exp,              "__builtin_exp",              "exp"},
373     {&intrin_mod,              "__builtin_mod",              "mod"},
374     {&intrin_pow,              "__builtin_pow",              "pow"},
375     {&intrin_isnan,            "__builtin_isnan",            "isnan"},
376     {&intrin_debug_typestring, "__builtin_debug_typestring", ""} 
377 };
378
379 void intrin_intrinsics_destroy(parser_t *parser) {
380     /*size_t i;*/
381     (void)parser;
382     util_htdel(intrin_intrinsics());
383 }
384
385
386 static 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].name, &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 (ast_expression*)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     /*
417      * check aliases now to see if there is an implementation of it.
418      */
419     for (i = 0; i < sizeof(intrinsics) / sizeof(*intrinsics); i++)
420         if (!strcmp(intrinsics[i].alias, name))
421             return intrinsics[i].intrin(parser);
422
423     parseerror(parser, "need function: `%s` compiler depends on it", name);
424     return NULL;
425 }