src/lj_ir.c

   1 /*
   2 ** SSA IR (Intermediate Representation) emitter.
   3 ** Copyright (C) 2005-2011 Mike Pall. See Copyright Notice in luajit.h
   4 */
   5
   6 #define lj_ir_c
   7 #define LUA_CORE
   8
   9 /* For pointers to libc/libm functions. */
  10 #include <stdio.h>
  11 #include <math.h>
  12
  13 #include "lj_obj.h"
  14
  15 #if LJ_HASJIT
  16
  17 #include "lj_gc.h"
  18 #include "lj_str.h"
  19 #include "lj_tab.h"
  20 #include "lj_ir.h"
  21 #include "lj_jit.h"
  22 #include "lj_iropt.h"
  23 #include "lj_trace.h"
  24 #if LJ_HASFFI
  25 #include "lj_ctype.h"
  26 #include "lj_cdata.h"
  27 #endif
  28 #include "lj_lib.h"
  29
  30 /* Some local macros to save typing. Undef'd at the end. */
  31 #define IR(ref)                 (&J->cur.ir[(ref)])
  32 #define fins                    (&J->fold.ins)
  33
  34 /* Pass IR on to next optimization in chain (FOLD). */
  35 #define emitir(ot, a, b)        (lj_ir_set(J, (ot), (a), (b)), lj_opt_fold(J))
  36
  37 /* -- IR tables ----------------------------------------------------------- */
  38
  39 /* IR instruction modes. */
  40 LJ_DATADEF const uint8_t lj_ir_mode[IR__MAX+1] = {
  41 IRDEF(IRMODE)
  42   0
  43 };
  44
  45 /* C call info for CALL* instructions. */
  46 LJ_DATADEF const CCallInfo lj_ir_callinfo[] = {
  47 #define IRCALLCI(name, nargs, kind, type, flags) \
  48   { (ASMFunction)name, \
  49     (nargs)|(CCI_CALL_##kind)|(IRT_##type<<CCI_OTSHIFT)|(flags) },
  50 IRCALLDEF(IRCALLCI)
  51 #undef IRCALLCI
  52   { NULL, 0 }
  53 };
  54
  55
  56 /* -- IR emitter ---------------------------------------------------------- */
  57
  58 /* Grow IR buffer at the top. */
  59 void LJ_FASTCALL lj_ir_growtop(jit_State *J)
  60 {
  61   IRIns *baseir = J->irbuf + J->irbotlim;
  62   MSize szins = J->irtoplim - J->irbotlim;
  63   if (szins) {
  64     baseir = (IRIns *)lj_mem_realloc(J->L, baseir, szins*sizeof(IRIns),
  65                                      2*szins*sizeof(IRIns));
  66     J->irtoplim = J->irbotlim + 2*szins;
  67   } else {
  68     baseir = (IRIns *)lj_mem_realloc(J->L, NULL, 0, LJ_MIN_IRSZ*sizeof(IRIns));
  69     J->irbotlim = REF_BASE - LJ_MIN_IRSZ/4;
  70     J->irtoplim = J->irbotlim + LJ_MIN_IRSZ;
  71   }
  72   J->cur.ir = J->irbuf = baseir - J->irbotlim;
  73 }
  74
  75 /* Grow IR buffer at the bottom or shift it up. */
  76 static void lj_ir_growbot(jit_State *J)
  77 {
  78   IRIns *baseir = J->irbuf + J->irbotlim;
  79   MSize szins = J->irtoplim - J->irbotlim;
  80   lua_assert(szins != 0);
  81   lua_assert(J->cur.nk == J->irbotlim);
  82   if (J->cur.nins + (szins >> 1) < J->irtoplim) {
  83     /* More than half of the buffer is free on top: shift up by a quarter. */
  84     MSize ofs = szins >> 2;
  85     memmove(baseir + ofs, baseir, (J->cur.nins - J->irbotlim)*sizeof(IRIns));
  86     J->irbotlim -= ofs;
  87     J->irtoplim -= ofs;
  88     J->cur.ir = J->irbuf = baseir - J->irbotlim;
  89   } else {
  90     /* Double the buffer size, but split the growth amongst top/bottom. */
  91     IRIns *newbase = lj_mem_newt(J->L, 2*szins*sizeof(IRIns), IRIns);
  92     MSize ofs = szins >= 256 ? 128 : (szins >> 1);  /* Limit bottom growth. */
  93     memcpy(newbase + ofs, baseir, (J->cur.nins - J->irbotlim)*sizeof(IRIns));
  94     lj_mem_free(G(J->L), baseir, szins*sizeof(IRIns));
  95     J->irbotlim -= ofs;
  96     J->irtoplim = J->irbotlim + 2*szins;
  97     J->cur.ir = J->irbuf = newbase - J->irbotlim;
  98   }
  99 }
 100
 101 /* Emit IR without any optimizations. */
 102 TRef LJ_FASTCALL lj_ir_emit(jit_State *J)
 103 {
 104   IRRef ref = lj_ir_nextins(J);
 105   IRIns *ir = IR(ref);
 106   IROp op = fins->o;
 107   ir->prev = J->chain[op];
 108   J->chain[op] = (IRRef1)ref;
 109   ir->o = op;
 110   ir->op1 = fins->op1;
 111   ir->op2 = fins->op2;
 112   J->guardemit.irt |= fins->t.irt;
 113   return TREF(ref, irt_t((ir->t = fins->t)));
 114 }
 115
 116 /* Emit call to a C function. */
 117 TRef lj_ir_call(jit_State *J, IRCallID id, ...)
 118 {
 119   const CCallInfo *ci = &lj_ir_callinfo[id];
 120   uint32_t n = CCI_NARGS(ci);
 121   TRef tr = TREF_NIL;
 122   va_list argp;
 123   va_start(argp, id);
 124   if ((ci->flags & CCI_L)) n--;
 125   if (n > 0)
 126     tr = va_arg(argp, IRRef);
 127   while (n-- > 1)
 128     tr = emitir(IRT(IR_CARG, IRT_NIL), tr, va_arg(argp, IRRef));
 129   va_end(argp);
 130   if (CCI_OP(ci) == IR_CALLS)
 131     J->needsnap = 1;  /* Need snapshot after call with side effect. */
 132   return emitir(CCI_OPTYPE(ci), tr, id);
 133 }
 134
 135 /* -- Interning of constants ---------------------------------------------- */
 136
 137 /*
 138 ** IR instructions for constants are kept between J->cur.nk >= ref < REF_BIAS.
 139 ** They are chained like all other instructions, but grow downwards.
 140 ** The are interned (like strings in the VM) to facilitate reference
 141 ** comparisons. The same constant must get the same reference.
 142 */
 143
 144 /* Get ref of next IR constant and optionally grow IR.
 145 ** Note: this may invalidate all IRIns *!
 146 */
 147 static LJ_AINLINE IRRef ir_nextk(jit_State *J)
 148 {
 149   IRRef ref = J->cur.nk;
 150   if (LJ_UNLIKELY(ref <= J->irbotlim)) lj_ir_growbot(J);
 151   J->cur.nk = --ref;
 152   return ref;
 153 }
 154
 155 /* Intern int32_t constant. */
 156 TRef LJ_FASTCALL lj_ir_kint(jit_State *J, int32_t k)
 157 {
 158   IRIns *ir, *cir = J->cur.ir;
 159   IRRef ref;
 160   for (ref = J->chain[IR_KINT]; ref; ref = cir[ref].prev)
 161     if (cir[ref].i == k)
 162       goto found;
 163   ref = ir_nextk(J);
 164   ir = IR(ref);
 165   ir->i = k;
 166   ir->t.irt = IRT_INT;
 167   ir->o = IR_KINT;
 168   ir->prev = J->chain[IR_KINT];
 169   J->chain[IR_KINT] = (IRRef1)ref;
 170 found:
 171   return TREF(ref, IRT_INT);
 172 }
 173
 174 /* The MRef inside the KNUM/KINT64 IR instructions holds the address of the
 175 ** 64 bit constant. The constants themselves are stored in a chained array
 176 ** and shared across traces.
 177 **
 178 ** Rationale for choosing this data structure:
 179 ** - The address of the constants is embedded in the generated machine code
 180 **   and must never move. A resizable array or hash table wouldn't work.
 181 ** - Most apps need very few non-32 bit integer constants (less than a dozen).
 182 ** - Linear search is hard to beat in terms of speed and low complexity.
 183 */
 184 typedef struct K64Array {
 185   MRef next;                    /* Pointer to next list. */
 186   MSize numk;                   /* Number of used elements in this array. */
 187   TValue k[LJ_MIN_K64SZ];       /* Array of constants. */
 188 } K64Array;
 189
 190 /* Free all chained arrays. */
 191 void lj_ir_k64_freeall(jit_State *J)
 192 {
 193   K64Array *k;
 194   for (k = mref(J->k64, K64Array); k; ) {
 195     K64Array *next = mref(k->next, K64Array);
 196     lj_mem_free(J2G(J), k, sizeof(K64Array));
 197     k = next;
 198   }
 199 }
 200
 201 /* Find 64 bit constant in chained array or add it. */
 202 cTValue *lj_ir_k64_find(jit_State *J, uint64_t u64)
 203 {
 204   K64Array *k, *kp = NULL;
 205   TValue *ntv;
 206   MSize idx;
 207   /* Search for the constant in the whole chain of arrays. */
 208   for (k = mref(J->k64, K64Array); k; k = mref(k->next, K64Array)) {
 209     kp = k;  /* Remember previous element in list. */
 210     for (idx = 0; idx < k->numk; idx++) {  /* Search one array. */
 211       TValue *tv = &k->k[idx];
 212       if (tv->u64 == u64)  /* Needed for +-0/NaN/absmask. */
 213         return tv;
 214     }
 215   }
 216   /* Constant was not found, need to add it. */
 217   if (!(kp && kp->numk < LJ_MIN_K64SZ)) {  /* Allocate a new array. */
 218     K64Array *kn = lj_mem_newt(J->L, sizeof(K64Array), K64Array);
 219     setmref(kn->next, NULL);
 220     kn->numk = 0;
 221     if (kp)
 222       setmref(kp->next, kn);  /* Chain to the end of the list. */
 223     else
 224       setmref(J->k64, kn);  /* Link first array. */
 225     kp = kn;
 226   }
 227   ntv = &kp->k[kp->numk++];  /* Add to current array. */
 228   ntv->u64 = u64;
 229   return ntv;
 230 }
 231
 232 /* Intern 64 bit constant, given by its address. */
 233 TRef lj_ir_k64(jit_State *J, IROp op, cTValue *tv)
 234 {
 235   IRIns *ir, *cir = J->cur.ir;
 236   IRRef ref;
 237   IRType t = op == IR_KNUM ? IRT_NUM : IRT_I64;
 238   for (ref = J->chain[op]; ref; ref = cir[ref].prev)
 239     if (ir_k64(&cir[ref]) == tv)
 240       goto found;
 241   ref = ir_nextk(J);
 242   ir = IR(ref);
 243   lua_assert(checkptr32(tv));
 244   setmref(ir->ptr, tv);
 245   ir->t.irt = t;
 246   ir->o = op;
 247   ir->prev = J->chain[op];
 248   J->chain[op] = (IRRef1)ref;
 249 found:
 250   return TREF(ref, t);
 251 }
 252
 253 /* Intern FP constant, given by its 64 bit pattern. */
 254 TRef lj_ir_knum_u64(jit_State *J, uint64_t u64)
 255 {
 256   return lj_ir_k64(J, IR_KNUM, lj_ir_k64_find(J, u64));
 257 }
 258
 259 /* Intern 64 bit integer constant. */
 260 TRef lj_ir_kint64(jit_State *J, uint64_t u64)
 261 {
 262   return lj_ir_k64(J, IR_KINT64, lj_ir_k64_find(J, u64));
 263 }
 264
 265 /* Check whether a number is int and return it. -0 is NOT considered an int. */
 266 static int numistrueint(lua_Number n, int32_t *kp)
 267 {
 268   int32_t k = lj_num2int(n);
 269   if (n == cast_num(k)) {
 270     if (kp) *kp = k;
 271     if (k == 0) {  /* Special check for -0. */
 272       TValue tv;
 273       setnumV(&tv, n);
 274       if (tv.u32.hi != 0)
 275         return 0;
 276     }
 277     return 1;
 278   }
 279   return 0;
 280 }
 281
 282 /* Intern number as int32_t constant if possible, otherwise as FP constant. */
 283 TRef lj_ir_knumint(jit_State *J, lua_Number n)
 284 {
 285   int32_t k;
 286   if (numistrueint(n, &k))
 287     return lj_ir_kint(J, k);
 288   else
 289     return lj_ir_knum(J, n);
 290 }
 291
 292 /* Intern GC object "constant". */
 293 TRef lj_ir_kgc(jit_State *J, GCobj *o, IRType t)
 294 {
 295   IRIns *ir, *cir = J->cur.ir;
 296   IRRef ref;
 297   lua_assert(!isdead(J2G(J), o));
 298   for (ref = J->chain[IR_KGC]; ref; ref = cir[ref].prev)
 299     if (ir_kgc(&cir[ref]) == o)
 300       goto found;
 301   ref = ir_nextk(J);
 302   ir = IR(ref);
 303   /* NOBARRIER: Current trace is a GC root. */
 304   setgcref(ir->gcr, o);
 305   ir->t.irt = (uint8_t)t;
 306   ir->o = IR_KGC;
 307   ir->prev = J->chain[IR_KGC];
 308   J->chain[IR_KGC] = (IRRef1)ref;
 309 found:
 310   return TREF(ref, t);
 311 }
 312
 313 /* Intern 32 bit pointer constant. */
 314 TRef lj_ir_kptr_(jit_State *J, IROp op, void *ptr)
 315 {
 316   IRIns *ir, *cir = J->cur.ir;
 317   IRRef ref;
 318   lua_assert((void *)(intptr_t)i32ptr(ptr) == ptr);
 319   for (ref = J->chain[op]; ref; ref = cir[ref].prev)
 320     if (mref(cir[ref].ptr, void) == ptr)
 321       goto found;
 322   ref = ir_nextk(J);
 323   ir = IR(ref);
 324   setmref(ir->ptr, ptr);
 325   ir->t.irt = IRT_P32;
 326   ir->o = op;
 327   ir->prev = J->chain[op];
 328   J->chain[op] = (IRRef1)ref;
 329 found:
 330   return TREF(ref, IRT_P32);
 331 }
 332
 333 /* Intern typed NULL constant. */
 334 TRef lj_ir_knull(jit_State *J, IRType t)
 335 {
 336   IRIns *ir, *cir = J->cur.ir;
 337   IRRef ref;
 338   for (ref = J->chain[IR_KNULL]; ref; ref = cir[ref].prev)
 339     if (irt_t(cir[ref].t) == t)
 340       goto found;
 341   ref = ir_nextk(J);
 342   ir = IR(ref);
 343   ir->i = 0;
 344   ir->t.irt = (uint8_t)t;
 345   ir->o = IR_KNULL;
 346   ir->prev = J->chain[IR_KNULL];
 347   J->chain[IR_KNULL] = (IRRef1)ref;
 348 found:
 349   return TREF(ref, t);
 350 }
 351
 352 /* Intern key slot. */
 353 TRef lj_ir_kslot(jit_State *J, TRef key, IRRef slot)
 354 {
 355   IRIns *ir, *cir = J->cur.ir;
 356   IRRef2 op12 = IRREF2((IRRef1)key, (IRRef1)slot);
 357   IRRef ref;
 358   /* Const part is not touched by CSE/DCE, so 0-65535 is ok for IRMlit here. */
 359   lua_assert(tref_isk(key) && slot == (IRRef)(IRRef1)slot);
 360   for (ref = J->chain[IR_KSLOT]; ref; ref = cir[ref].prev)
 361     if (cir[ref].op12 == op12)
 362       goto found;
 363   ref = ir_nextk(J);
 364   ir = IR(ref);
 365   ir->op12 = op12;
 366   ir->t.irt = IRT_P32;
 367   ir->o = IR_KSLOT;
 368   ir->prev = J->chain[IR_KSLOT];
 369   J->chain[IR_KSLOT] = (IRRef1)ref;
 370 found:
 371   return TREF(ref, IRT_P32);
 372 }
 373
 374 /* -- Access to IR constants ---------------------------------------------- */
 375
 376 /* Copy value of IR constant. */
 377 void lj_ir_kvalue(lua_State *L, TValue *tv, const IRIns *ir)
 378 {
 379   UNUSED(L);
 380   lua_assert(ir->o != IR_KSLOT);  /* Common mistake. */
 381   switch (ir->o) {
 382   case IR_KPRI: setitype(tv, irt_toitype(ir->t)); break;
 383   case IR_KINT: setintV(tv, ir->i); break;
 384   case IR_KGC: setgcV(L, tv, ir_kgc(ir), irt_toitype(ir->t)); break;
 385   case IR_KPTR: case IR_KKPTR: case IR_KNULL:
 386     setlightudV(tv, mref(ir->ptr, void));
 387     break;
 388   case IR_KNUM: setnumV(tv, ir_knum(ir)->n); break;
 389 #if LJ_HASFFI
 390   case IR_KINT64: {
 391     GCcdata *cd = lj_cdata_new_(L, CTID_INT64, 8);
 392     *(uint64_t *)cdataptr(cd) = ir_kint64(ir)->u64;
 393     setcdataV(L, tv, cd);
 394     break;
 395     }
 396 #endif
 397   default: lua_assert(0); break;
 398   }
 399 }
 400
 401 /* -- Convert IR operand types -------------------------------------------- */
 402
 403 /* Convert from integer or string to number. */
 404 TRef LJ_FASTCALL lj_ir_tonum(jit_State *J, TRef tr)
 405 {
 406   if (!tref_isnum(tr)) {
 407     if (tref_isinteger(tr))
 408       tr = emitir(IRTN(IR_CONV), tr, IRCONV_NUM_INT);
 409     else if (tref_isstr(tr))
 410       tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
 411     else
 412       lj_trace_err(J, LJ_TRERR_BADTYPE);
 413   }
 414   return tr;
 415 }
 416
 417 /* Convert from integer or number to string. */
 418 TRef LJ_FASTCALL lj_ir_tostr(jit_State *J, TRef tr)
 419 {
 420   if (!tref_isstr(tr)) {
 421     if (!tref_isnumber(tr))
 422       lj_trace_err(J, LJ_TRERR_BADTYPE);
 423     tr = emitir(IRT(IR_TOSTR, IRT_STR), tr, 0);
 424   }
 425   return tr;
 426 }
 427
 428 /* Convert from number or string to bitop operand (overflow wrapped). */
 429 TRef LJ_FASTCALL lj_ir_tobit(jit_State *J, TRef tr)
 430 {
 431   if (!tref_isinteger(tr)) {
 432     if (tref_isstr(tr))
 433       tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
 434     else if (!tref_isnum(tr))
 435       lj_trace_err(J, LJ_TRERR_BADTYPE);
 436     tr = emitir(IRTI(IR_TOBIT), tr, lj_ir_knum_tobit(J));
 437   }
 438   return tr;
 439 }
 440
 441 /* Convert from number or string to integer (overflow undefined). */
 442 TRef LJ_FASTCALL lj_ir_toint(jit_State *J, TRef tr)
 443 {
 444   if (!tref_isinteger(tr)) {
 445     if (tref_isstr(tr))
 446       tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
 447     else if (!tref_isnum(tr))
 448       lj_trace_err(J, LJ_TRERR_BADTYPE);
 449     tr = emitir(IRTI(IR_CONV), tr, IRCONV_INT_NUM|IRCONV_ANY);
 450   }
 451   return tr;
 452 }
 453
 454 /* -- Miscellaneous IR ops ------------------------------------------------ */
 455
 456 /* Evaluate numeric comparison. */
 457 int lj_ir_numcmp(lua_Number a, lua_Number b, IROp op)
 458 {
 459   switch (op) {
 460   case IR_EQ: return (a == b);
 461   case IR_NE: return (a != b);
 462   case IR_LT: return (a < b);
 463   case IR_GE: return (a >= b);
 464   case IR_LE: return (a <= b);
 465   case IR_GT: return (a > b);
 466   case IR_ULT: return !(a >= b);
 467   case IR_UGE: return !(a < b);
 468   case IR_ULE: return !(a > b);
 469   case IR_UGT: return !(a <= b);
 470   default: lua_assert(0); return 0;
 471   }
 472 }
 473
 474 /* Evaluate string comparison. */
 475 int lj_ir_strcmp(GCstr *a, GCstr *b, IROp op)
 476 {
 477   int res = lj_str_cmp(a, b);
 478   switch (op) {
 479   case IR_LT: return (res < 0);
 480   case IR_GE: return (res >= 0);
 481   case IR_LE: return (res <= 0);
 482   case IR_GT: return (res > 0);
 483   default: lua_assert(0); return 0;
 484   }
 485 }
 486
 487 /* Rollback IR to previous state. */
 488 void lj_ir_rollback(jit_State *J, IRRef ref)
 489 {
 490   IRRef nins = J->cur.nins;
 491   while (nins > ref) {
 492     IRIns *ir;
 493     nins--;
 494     ir = IR(nins);
 495     J->chain[ir->o] = ir->prev;
 496   }
 497   J->cur.nins = nins;
 498 }
 499
 500 #undef IR
 501 #undef fins
 502 #undef emitir
 503
 504 #endif