src/buildvm_fold.c

   1 /*
   2 ** LuaJIT VM builder: IR folding hash table generator.
   3 ** Copyright (C) 2005-2011 Mike Pall. See Copyright Notice in luajit.h
   4 */
   5
   6 #include "buildvm.h"
   7 #include "lj_obj.h"
   8 #include "lj_ir.h"
   9
  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;
  15
  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 }
  48
  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 }
  59
  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 }
  91
  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 }
 140
 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 }
 166
 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;
 173
 174   if (fname == NULL) {
 175     fprintf(stderr, "Error: missing input filename\n");
 176     exit(1);
 177   }
 178
 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   }
 189
 190   fprintf(ctx->fp, "/* This is a generated file. DO NOT EDIT! */\n\n");
 191   fprintf(ctx->fp, "static const FoldFunc fold_func[] = {\n");
 192
 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");
 226
 227   makehash(ctx);
 228 }
 229