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 a, float b) {
 208      *     float div = a / b;
 209      *     float sign = (div < 0.0f) ? -1 : 1;
 210      *     return a - b * sign * floor(sign * div);
 211      * }
 212      */
 213     ast_value    *value = NULL;
 214     ast_call     *call  = ast_call_new (intrin_ctx(intrin), intrin_func(intrin, "floor"));
 215     ast_value    *a     = ast_value_new(intrin_ctx(intrin), "a",    TYPE_FLOAT);
 216     ast_value    *b     = ast_value_new(intrin_ctx(intrin), "b",    TYPE_FLOAT);
 217     ast_value    *div   = ast_value_new(intrin_ctx(intrin), "div",  TYPE_FLOAT);
 218     ast_value    *sign  = ast_value_new(intrin_ctx(intrin), "sign", TYPE_FLOAT);
 219     ast_block    *body  = ast_block_new(intrin_ctx(intrin));
 220     ast_function *func  = intrin_value(intrin, &value, "mod", TYPE_FLOAT);
 221
 222     vec_push(value->expression.params, a);
 223     vec_push(value->expression.params, b);
 224
 225     vec_push(body->locals, div);
 226     vec_push(body->locals, sign);
 227
 228     /* div = a / b; */
 229     vec_push(body->exprs,
 230         (ast_expression*)ast_store_new(
 231             intrin_ctx(intrin),
 232             INSTR_STORE_F,
 233             (ast_expression*)div,
 234             (ast_expression*)ast_binary_new(
 235                 intrin_ctx(intrin),
 236                 INSTR_DIV_F,
 237                 (ast_expression*)a,
 238                 (ast_expression*)b
 239             )
 240         )
 241     );
 242
 243     /* sign = (div < 0.0f) ? -1 : 1; */
 244     vec_push(body->exprs,
 245         (ast_expression*)ast_store_new(
 246             intrin_ctx(intrin),
 247             INSTR_STORE_F,
 248             (ast_expression*)sign,
 249             (ast_expression*)ast_ternary_new(
 250                 intrin_ctx(intrin),
 251                 (ast_expression*)ast_binary_new(
 252                     intrin_ctx(intrin),
 253                     INSTR_LT,
 254                     (ast_expression*)div,
 255                     (ast_expression*)intrin->fold->imm_float[0]
 256                 ),
 257                 (ast_expression*)intrin->fold->imm_float[2],
 258                 (ast_expression*)intrin->fold->imm_float[1]
 259             )
 260         )
 261     );
 262
 263     /* floor(sign * div) */
 264     vec_push(call->params,
 265         (ast_expression*)ast_binary_new(
 266             intrin_ctx(intrin),
 267             INSTR_MUL_F,
 268             (ast_expression*)sign,
 269             (ast_expression*)div
 270         )
 271     );
 272
 273     /* return a - b * sign * <call> */
 274     vec_push(body->exprs,
 275         (ast_expression*)ast_return_new(
 276             intrin_ctx(intrin),
 277             (ast_expression*)ast_binary_new(
 278                 intrin_ctx(intrin),
 279                 INSTR_SUB_F,
 280                 (ast_expression*)a,
 281                 (ast_expression*)ast_binary_new(
 282                     intrin_ctx(intrin),
 283                     INSTR_MUL_F,
 284                     (ast_expression*)b,
 285                     (ast_expression*)ast_binary_new(
 286                         intrin_ctx(intrin),
 287                         INSTR_MUL_F,
 288                         (ast_expression*)sign,
 289                         (ast_expression*)call
 290                     )
 291                 )
 292             )
 293         )
 294     );
 295
 296     vec_push(func->blocks, body); /* {{{ body }}} */
 297     intrin_reg(intrin, value, func);
 298
 299     return (ast_expression*)value;
 300 }
 301
 302 static ast_expression *intrin_exp(intrin_t *intrin) {
 303     /*
 304      * float exp(float x) {
 305      *     return pow(QC_M_E, x);
 306      * }
 307      */
 308     ast_value    *value = NULL;
 309     ast_call     *call  = ast_call_new (intrin_ctx(intrin), intrin_func(intrin, "pow"));
 310     ast_value    *arg1  = ast_value_new(intrin_ctx(intrin), "x", TYPE_FLOAT);
 311     ast_block    *body  = ast_block_new(intrin_ctx(intrin));
 312     ast_function *func  = intrin_value(intrin, &value, "exp", TYPE_FLOAT);
 313
 314     /* push arguments for params to call */
 315     vec_push(call->params, (ast_expression*)fold_constgen_float(intrin->fold, QC_M_E));
 316     vec_push(call->params, (ast_expression*)arg1);
 317
 318     /* return pow(QC_M_E, x) */
 319     vec_push(body->exprs,
 320         (ast_expression*)ast_return_new(
 321             intrin_ctx(intrin),
 322             (ast_expression*)call
 323         )
 324     );
 325
 326     vec_push(value->expression.params, arg1); /* float x (for param) */
 327
 328     vec_push(func->blocks,             body); /* {{{ body }}} */
 329
 330     intrin_reg(intrin, value, func);
 331
 332     return (ast_expression*)value;
 333 }
 334
 335 static ast_expression *intrin_isnan(intrin_t *intrin) {
 336     /*
 337      * float isnan(float x) {
 338      *   float local;
 339      *   local = x;
 340      *
 341      *   return (x != local);
 342      * }
 343      */
 344     ast_value    *value  = NULL;
 345     ast_value    *arg1   = ast_value_new(intrin_ctx(intrin), "x",     TYPE_FLOAT);
 346     ast_value    *local  = ast_value_new(intrin_ctx(intrin), "local", TYPE_FLOAT);
 347     ast_block    *body   = ast_block_new(intrin_ctx(intrin));
 348     ast_function *func   = intrin_value(intrin, &value, "isnan", TYPE_FLOAT);
 349
 350     vec_push(body->locals, local);
 351     vec_push(body->exprs,
 352         (ast_expression*)ast_store_new(
 353             intrin_ctx(intrin),
 354             INSTR_STORE_F,
 355             (ast_expression*)local,
 356             (ast_expression*)arg1
 357         )
 358     );
 359
 360     vec_push(body->exprs,
 361         (ast_expression*)ast_return_new(
 362             intrin_ctx(intrin),
 363             (ast_expression*)ast_binary_new(
 364                 intrin_ctx(intrin),
 365                 INSTR_NE_F,
 366                 (ast_expression*)arg1,
 367                 (ast_expression*)local
 368             )
 369         )
 370     );
 371
 372     vec_push(value->expression.params, arg1);
 373     vec_push(func->blocks, body);
 374
 375     intrin_reg(intrin, value, func);
 376
 377     return (ast_expression*)value;
 378 }
 379
 380 static ast_expression *intrin_fabs(intrin_t *intrin) {
 381     /*
 382      * float fabs(float x) {
 383      *     return x < 0 ? -x : x;
 384      * }
 385      */
 386     ast_value    *value  = NULL;
 387     ast_value    *arg1   = ast_value_new(intrin_ctx(intrin), "x", TYPE_FLOAT);
 388     ast_block    *body   = ast_block_new(intrin_ctx(intrin));
 389     ast_function *func   = intrin_value(intrin, &value, "fabs", TYPE_FLOAT);
 390
 391     vec_push(body->exprs,
 392         (ast_expression*)ast_return_new(
 393             intrin_ctx(intrin),
 394             (ast_expression*)ast_ternary_new(
 395                 intrin_ctx(intrin),
 396                 (ast_expression*)ast_binary_new(
 397                     intrin_ctx(intrin),
 398                     INSTR_LE,
 399                     (ast_expression*)arg1,
 400                     (ast_expression*)intrin->fold->imm_float[0]
 401                 ),
 402                 (ast_expression*)ast_binary_new(
 403                     intrin_ctx(intrin),
 404                     INSTR_SUB_F,
 405                     (ast_expression*)intrin->fold->imm_float[0],
 406                     (ast_expression*)arg1
 407                 ),
 408                 (ast_expression*)arg1
 409             )
 410         )
 411     );
 412
 413     vec_push(value->expression.params, arg1);
 414     vec_push(func->blocks, body);
 415
 416     intrin_reg(intrin, value, func);
 417
 418     return (ast_expression*)value;
 419 }
 420
 421 /*
 422  * TODO: make static (and handle ast_type_string) here for the builtin
 423  * instead of in SYA parse close.
 424  */
 425 ast_expression *intrin_debug_typestring(intrin_t *intrin) {
 426     (void)intrin;
 427     return (ast_expression*)0x1;
 428 }
 429
 430 static const intrin_func_t intrinsics[] = {
 431     {&intrin_exp,              "__builtin_exp",              "exp",   1},
 432     {&intrin_mod,              "__builtin_mod",              "mod",   2},
 433     {&intrin_pow,              "__builtin_pow",              "pow",   2},
 434     {&intrin_isnan,            "__builtin_isnan",            "isnan", 1},
 435     {&intrin_fabs,             "__builtin_fabs",             "fabs",  1},
 436     {&intrin_debug_typestring, "__builtin_debug_typestring", "",      0}
 437 };
 438
 439 static void intrin_error(intrin_t *intrin, const char *fmt, ...) {
 440     va_list ap;
 441     va_start(ap, fmt);
 442     vcompile_error(intrin->parser->lex->tok.ctx, fmt, ap);
 443     va_end(ap);
 444 }
 445
 446 /* exposed */
 447 intrin_t *intrin_init(parser_t *parser) {
 448     intrin_t *intrin = (intrin_t*)mem_a(sizeof(intrin_t));
 449     size_t    i;
 450
 451     intrin->parser     = parser;
 452     intrin->fold       = parser->fold;
 453     intrin->intrinsics = NULL;
 454     intrin->generated  = NULL;
 455
 456     vec_append(intrin->intrinsics, GMQCC_ARRAY_COUNT(intrinsics), intrinsics);
 457
 458     /* populate with null pointers for tracking generation */
 459     for (i = 0; i < GMQCC_ARRAY_COUNT(intrinsics); i++)
 460         vec_push(intrin->generated, NULL);
 461
 462     return intrin;
 463 }
 464
 465 void intrin_cleanup(intrin_t *intrin) {
 466     vec_free(intrin->intrinsics);
 467     vec_free(intrin->generated);
 468     mem_d(intrin);
 469 }
 470
 471 ast_expression *intrin_fold(intrin_t *intrin, ast_value *value, ast_expression **exprs) {
 472     size_t i;
 473     if (!value || !value->name)
 474         return NULL;
 475     for (i = 0; i < vec_size(intrin->intrinsics); i++)
 476         if (!strcmp(value->name, intrin->intrinsics[i].name))
 477             return (vec_size(exprs) != intrin->intrinsics[i].args)
 478                         ? NULL
 479                         : fold_intrin(intrin->fold, value->name + 10, exprs);
 480     return NULL;
 481 }
 482
 483 static GMQCC_INLINE ast_expression *intrin_func_try(intrin_t *intrin, size_t offset, const char *compare) {
 484     size_t i;
 485     for (i = 0; i < vec_size(intrin->intrinsics); i++) {
 486         if (strcmp(*(char **)((char *)&intrin->intrinsics[i] + offset), compare))
 487             continue;
 488         if (intrin->generated[i])
 489             return intrin->generated[i];
 490         return intrin->generated[i] = intrin->intrinsics[i].intrin(intrin);
 491     }
 492     return NULL;
 493 }
 494
 495 ast_expression *intrin_func(intrin_t *intrin, const char *name) {
 496     size_t           i;
 497     ast_expression  *find;
 498
 499     /* try current first */
 500     if ((find = parser_find_global(intrin->parser, name)) && ((ast_value*)find)->expression.vtype == TYPE_FUNCTION)
 501         for (i = 0; i < vec_size(intrin->parser->functions); ++i)
 502             if (((ast_value*)find)->name && !strcmp(intrin->parser->functions[i]->name, ((ast_value*)find)->name) && intrin->parser->functions[i]->builtin < 0)
 503                 return find;
 504     /* try name second */
 505     if ((find = intrin_func_try(intrin, offsetof(intrin_func_t, name),  name)))
 506         return find;
 507     /* try alias third */
 508     if ((find = intrin_func_try(intrin, offsetof(intrin_func_t, alias), name)))
 509         return find;
 510
 511     intrin_error(intrin, "need function: `%s` compiler depends on it", name);
 512     return NULL;
 513 }