One Level Up Top Level

src/host/buildvm_fold.c - luajit-2.0-src

Global variables defined

Functions defined

Source code

  1. /*
  2. ** LuaJIT VM builder: IR folding hash table generator.
  3. ** Copyright (C) 2005-2015 Mike Pall. See Copyright Notice in luajit.h
  4. */

  6. #include "buildvm.h"
  7. #include "lj_obj.h"
  8. #include "lj_ir.h"

  10. /* Context for the folding hash table generator. */
  11. ‌static int lineno;
  12. ‌static int funcidx;
  13. ‌static uint32_t foldkeys[BUILD_MAX_FOLD];
  14. ‌static uint32_t nkeys;

  16. /* Try to fill the hash table with keys using the hash parameters. */
  17. ‌static int tryhash(uint32_t *htab, uint32_t sz, uint32_t r, int dorol)
  18. {
  19.   uint32_t i;
  20.   if (dorol && ((r & 31) == 0 || (r>>5) == 0))
  21.     return 0;  /* Avoid zero rotates. */
  22.   memset(htab, 0xff, (sz+1)*sizeof(uint32_t));
  23.   for (i = 0; i < nkeys; i++) {
  24.     uint32_t key = foldkeys[i];
  25.     uint32_t k = key & 0xffffff;
  26.     uint32_t h = (dorol ? lj_rol(lj_rol(k, r>>5) - k, r&31) :
  27.                           (((k << (r>>5)) - k) << (r&31))) % sz;
  28.     if (htab[h] != 0xffffffff) {  /* Collision on primary slot. */
  29.       if (htab[h+1] != 0xffffffff) {  /* Collision on secondary slot. */
  30.         /* Try to move the colliding key, if possible. */
  31.         if (h < sz-1 && htab[h+2] == 0xffffffff) {
  32.           uint32_t k2 = htab[h+1] & 0xffffff;
  33.           uint32_t h2 = (dorol ? lj_rol(lj_rol(k2, r>>5) - k2, r&31) :
  34.                                  (((k2 << (r>>5)) - k2) << (r&31))) % sz;
  35.           if (h2 != h+1) return 0;  /* Cannot resolve collision. */
  36.           htab[h+2] = htab[h+1];  /* Move colliding key to secondary slot. */
  37.         } else {
  38.           return 0;  /* Collision. */
  39.         }
  40.       }
  41.       htab[h+1] = key;
  42.     } else {
  43.       htab[h] = key;
  44.     }
  45.   }
  46.   return 1;  /* Success, all keys could be stored. */
  47. }

  49. /* Print the generated hash table. */
  50. ‌static void printhash(BuildCtx *ctx, uint32_t *htab, uint32_t sz)
  51. {
  52.   uint32_t i;
  53.   fprintf(ctx->fp, "static const uint32_t fold_hash[%d] = {\n0x%08x",
  54.           sz+1, htab[0]);
  55.   for (i = 1; i < sz+1; i++)
  56.     fprintf(ctx->fp, ",\n0x%08x", htab[i]);
  57.   fprintf(ctx->fp, "\n};\n\n");
  58. }

  60. /* Exhaustive search for the shortest semi-perfect hash table. */
  61. ‌static void makehash(BuildCtx *ctx)
  62. {
  63.   uint32_t htab[BUILD_MAX_FOLD*2+1];
  64.   uint32_t sz, r;
  65.   /* Search for the smallest hash table with an odd size. */
  66.   for (sz = (nkeys|1); sz < BUILD_MAX_FOLD*2; sz += 2) {
  67.     /* First try all shift hash combinations. */
  68.     for (r = 0; r < 32*32; r++) {
  69.       if (tryhash(htab, sz, r, 0)) {
  70.         printhash(ctx, htab, sz);
  71.         fprintf(ctx->fp,
  72.                 "#define fold_hashkey(k)\t(((((k)<<%u)-(k))<<%u)%%%u)\n\n",
  73.                 r>>5, r&31, sz);
  74.         return;
  75.       }
  76.     }
  77.     /* Then try all rotate hash combinations. */
  78.     for (r = 0; r < 32*32; r++) {
  79.       if (tryhash(htab, sz, r, 1)) {
  80.         printhash(ctx, htab, sz);
  81.         fprintf(ctx->fp,
  82.           "#define fold_hashkey(k)\t(lj_rol(lj_rol((k),%u)-(k),%u)%%%u)\n\n",
  83.                 r>>5, r&31, sz);
  84.         return;
  85.       }
  86.     }
  87.   }
  88.   fprintf(stderr, "Error: search for perfect hash failed\n");
  89.   exit(1);
  90. }

  92. /* Parse one token of a fold rule. */
  93. ‌static uint32_t nexttoken(char **pp, int allowlit, int allowany)
  94. {
  95.   char *p = *pp;
  96.   if (p) {
  97.     uint32_t i;
  98.     char *q = strchr(p, ' ');
  99.     if (q) *q++ = '\0';
  100.     *pp = q;
  101.     if (allowlit && !strncmp(p, "IRFPM_", 6)) {
  102.       for (i = 0; irfpm_names[i]; i++)
  103.         if (!strcmp(irfpm_names[i], p+6))
  104.           return i;
  105.     } else if (allowlit && !strncmp(p, "IRFL_", 5)) {
  106.       for (i = 0; irfield_names[i]; i++)
  107.         if (!strcmp(irfield_names[i], p+5))
  108.           return i;
  109.     } else if (allowlit && !strncmp(p, "IRCALL_", 7)) {
  110.       for (i = 0; ircall_names[i]; i++)
  111.         if (!strcmp(ircall_names[i], p+7))
  112.           return i;
  113.     } else if (allowlit && !strncmp(p, "IRCONV_", 7)) {
  114.       for (i = 0; irt_names[i]; i++) {
  115.         const char *r = strchr(p+7, '_');
  116.         if (r && !strncmp(irt_names[i], p+7, r-(p+7))) {
  117.           uint32_t j;
  118.           for (j = 0; irt_names[j]; j++)
  119.             if (!strcmp(irt_names[j], r+1))
  120.               return (i << 5) + j;
  121.         }
  122.       }
  123.     } else if (allowlit && *p >= '0' && *p <= '9') {
  124.       for (i = 0; *p >= '0' && *p <= '9'; p++)
  125.         i = i*10 + (*p - '0');
  126.       if (*p == '\0')
  127.         return i;
  128.     } else if (allowany && !strcmp("any", p)) {
  129.       return allowany;
  130.     } else {
  131.       for (i = 0; ir_names[i]; i++)
  132.         if (!strcmp(ir_names[i], p))
  133.           return i;
  134.     }
  135.     fprintf(stderr, "Error: bad fold definition token \"%s\" at line %d\n", p, lineno);
  136.     exit(1);
  137.   }
  138.   return 0;
  139. }

  141. /* Parse a fold rule. */
  142. ‌static void foldrule(char *p)
  143. {
  144.   uint32_t op = nexttoken(&p, 0, 0);
  145.   uint32_t left = nexttoken(&p, 0, 0x7f);
  146.   uint32_t right = nexttoken(&p, 1, 0x3ff);
  147.   uint32_t key = (funcidx << 24) | (op << 17) | (left << 10) | right;
  148.   uint32_t i;
  149.   if (nkeys >= BUILD_MAX_FOLD) {
  150.     fprintf(stderr, "Error: too many fold rules, increase BUILD_MAX_FOLD.\n");
  151.     exit(1);
  152.   }
  153.   /* Simple insertion sort to detect duplicates. */
  154.   for (i = nkeys; i > 0; i--) {
  155.     if ((foldkeys[i-1]&0xffffff) < (key & 0xffffff))
  156.       break;
  157.     if ((foldkeys[i-1]&0xffffff) == (key & 0xffffff)) {
  158.       fprintf(stderr, "Error: duplicate fold definition at line %d\n", lineno);
  159.       exit(1);
  160.     }
  161.     foldkeys[i] = foldkeys[i-1];
  162.   }
  163.   foldkeys[i] = key;
  164.   nkeys++;
  165. }

  167. /* Emit C source code for IR folding hash table. */
  168. ‌void emit_fold(BuildCtx *ctx)
  169. {
  170.   char buf[256];  /* We don't care about analyzing lines longer than that. */
  171.   const char *fname = ctx->args[0];
  172.   FILE *fp;

  174.   if (fname == NULL) {
  175.     fprintf(stderr, "Error: missing input filename\n");
  176.     exit(1);
  177.   }

  179.   if (fname[0] == '-' && fname[1] == '\0') {
  180.     fp = stdin;
  181.   } else {
  182.     fp = fopen(fname, "r");
  183.     if (!fp) {
  184.       fprintf(stderr, "Error: cannot open input file '%s': %s\n",
  185.               fname, strerror(errno));
  186.       exit(1);
  187.     }
  188.   }

  190.   fprintf(ctx->fp, "/* This is a generated file. DO NOT EDIT! */\n\n");
  191.   fprintf(ctx->fp, "static const FoldFunc fold_func[] = {\n");

  193.   lineno = 0;
  194.   funcidx = 0;
  195.   nkeys = 0;
  196.   while (fgets(buf, sizeof(buf), fp) != NULL) {
  197.     lineno++;
  198.     /* The prefix must be at the start of a line, otherwise it's ignored. */
  199.     if (!strncmp(buf, FOLDDEF_PREFIX, sizeof(FOLDDEF_PREFIX)-1)) {
  200.       char *p = buf+sizeof(FOLDDEF_PREFIX)-1;
  201.       char *q = strchr(p, ')');
  202.       if (p[0] == '(' && q) {
  203.         p++;
  204.         *q = '\0';
  205.         foldrule(p);
  206.       } else if ((p[0] == 'F' || p[0] == 'X') && p[1] == '(' && q) {
  207.         p += 2;
  208.         *q = '\0';
  209.         if (funcidx)
  210.           fprintf(ctx->fp, ",\n");
  211.         if (p[-2] == 'X')
  212.           fprintf(ctx->fp, "  %s", p);
  213.         else
  214.           fprintf(ctx->fp, "  fold_%s", p);
  215.         funcidx++;
  216.       } else {
  217.         buf[strlen(buf)-1] = '\0';
  218.         fprintf(stderr, "Error: unknown fold definition tag %s%s at line %d\n",
  219.                 FOLDDEF_PREFIX, p, lineno);
  220.         exit(1);
  221.       }
  222.     }
  223.   }
  224.   fclose(fp);
  225.   fprintf(ctx->fp, "\n};\n\n");

  227.   makehash(ctx);
  228. }

One Level Up Top Level