One Level Up Top Level

src/lj_ir.c - luajit-2.0-src

Global variables defined

Data types defined

Functions defined

Macros defined

Source code

  1. /*
  2. ** SSA IR (Intermediate Representation) emitter.
  3. ** Copyright (C) 2005-2015 Mike Pall. See Copyright Notice in luajit.h
  4. */

  6. ‌#define lj_ir_c
  7. ‌#define LUA_CORE

  9. /* For pointers to libc/libm functions. */
  10. #include <stdio.h>
  11. #include <math.h>

  13. #include "lj_obj.h"

  15. #if LJ_HASJIT

  17. #include "lj_gc.h"
  18. #include "lj_buf.h"
  19. #include "lj_str.h"
  20. #include "lj_tab.h"
  21. #include "lj_ir.h"
  22. #include "lj_jit.h"
  23. #include "lj_ircall.h"
  24. #include "lj_iropt.h"
  25. #include "lj_trace.h"
  26. #if LJ_HASFFI
  27. #include "lj_ctype.h"
  28. #include "lj_cdata.h"
  29. #include "lj_carith.h"
  30. #endif
  31. #include "lj_vm.h"
  32. #include "lj_strscan.h"
  33. #include "lj_strfmt.h"
  34. #include "lj_lib.h"

  36. /* Some local macros to save typing. Undef'd at the end. */
  37. ‌#define IR(ref)                        (&J->cur.ir[(ref)])
  38. ‌#define fins                        (&J->fold.ins)

  40. /* Pass IR on to next optimization in chain (FOLD). */
  41. ‌#define emitir(ot, a, b)        (lj_ir_set(J, (ot), (a), (b)), lj_opt_fold(J))

  43. /* -- IR tables ----------------------------------------------------------- */

  45. /* IR instruction modes. */
  46. ‌LJ_DATADEF const uint8_t lj_ir_mode[IR__MAX+1] = {
  47. IRDEF(IRMODE)
  48.   0
  49. };

  51. /* IR type sizes. */
  52. ‌LJ_DATADEF const uint8_t lj_ir_type_size[IRT__MAX+1] = {
  53. ‌#define IRTSIZE(name, size)        size,
  54. IRTDEF(IRTSIZE)
  55. ‌#undef IRTSIZE
  56.   0
  57. };

  59. /* C call info for CALL* instructions. */
  60. ‌LJ_DATADEF const CCallInfo lj_ir_callinfo[] = {
  61. ‌#define IRCALLCI(cond, name, nargs, kind, type, flags) \
  62.   { (ASMFunction)IRCALLCOND_##cond(name), \
  63.     (nargs)|(CCI_CALL_##kind)|(IRT_##type<<CCI_OTSHIFT)|(flags) },
  64. IRCALLDEF(IRCALLCI)
  65. ‌#undef IRCALLCI
  66.   { NULL, 0 }
  67. };

  69. /* -- IR emitter ---------------------------------------------------------- */

  71. /* Grow IR buffer at the top. */
  72. ‌void LJ_FASTCALL lj_ir_growtop(jit_State *J)
  73. {
  74.   IRIns *baseir = J->irbuf + J->irbotlim;
  75.   MSize szins = J->irtoplim - J->irbotlim;
  76.   if (szins) {
  77.     baseir = (IRIns *)lj_mem_realloc(J->L, baseir, szins*sizeof(IRIns),
  78.                                      2*szins*sizeof(IRIns));
  79.     J->irtoplim = J->irbotlim + 2*szins;
  80.   } else {
  81.     baseir = (IRIns *)lj_mem_realloc(J->L, NULL, 0, LJ_MIN_IRSZ*sizeof(IRIns));
  82.     J->irbotlim = REF_BASE - LJ_MIN_IRSZ/4;
  83.     J->irtoplim = J->irbotlim + LJ_MIN_IRSZ;
  84.   }
  85.   J->cur.ir = J->irbuf = baseir - J->irbotlim;
  86. }

  88. /* Grow IR buffer at the bottom or shift it up. */
  89. ‌static void lj_ir_growbot(jit_State *J)
  90. {
  91.   IRIns *baseir = J->irbuf + J->irbotlim;
  92.   MSize szins = J->irtoplim - J->irbotlim;
  93.   lua_assert(szins != 0);
  94.   lua_assert(J->cur.nk == J->irbotlim);
  95.   if (J->cur.nins + (szins >> 1) < J->irtoplim) {
  96.     /* More than half of the buffer is free on top: shift up by a quarter. */
  97.     MSize ofs = szins >> 2;
  98.     memmove(baseir + ofs, baseir, (J->cur.nins - J->irbotlim)*sizeof(IRIns));
  99.     J->irbotlim -= ofs;
  100.     J->irtoplim -= ofs;
  101.     J->cur.ir = J->irbuf = baseir - J->irbotlim;
  102.   } else {
  103.     /* Double the buffer size, but split the growth amongst top/bottom. */
  104.     IRIns *newbase = lj_mem_newt(J->L, 2*szins*sizeof(IRIns), IRIns);
  105.     MSize ofs = szins >= 256 ? 128 : (szins >> 1);  /* Limit bottom growth. */
  106.     memcpy(newbase + ofs, baseir, (J->cur.nins - J->irbotlim)*sizeof(IRIns));
  107.     lj_mem_free(G(J->L), baseir, szins*sizeof(IRIns));
  108.     J->irbotlim -= ofs;
  109.     J->irtoplim = J->irbotlim + 2*szins;
  110.     J->cur.ir = J->irbuf = newbase - J->irbotlim;
  111.   }
  112. }

  114. /* Emit IR without any optimizations. */
  115. ‌TRef LJ_FASTCALL lj_ir_emit(jit_State *J)
  116. {
  117.   IRRef ref = lj_ir_nextins(J);
  118.   IRIns *ir = IR(ref);
  119.   IROp op = fins->o;
  120.   ir->prev = J->chain[op];
  121.   J->chain[op] = (IRRef1)ref;
  122.   ir->o = op;
  123.   ir->op1 = fins->op1;
  124.   ir->op2 = fins->op2;
  125.   J->guardemit.irt |= fins->t.irt;
  126.   return TREF(ref, irt_t((ir->t = fins->t)));
  127. }

  129. /* Emit call to a C function. */
  130. ‌TRef lj_ir_call(jit_State *J, IRCallID id, ...)
  131. {
  132.   const CCallInfo *ci = &lj_ir_callinfo[id];
  133.   uint32_t n = CCI_NARGS(ci);
  134.   TRef tr = TREF_NIL;
  135.   va_list argp;
  136.   va_start(argp, id);
  137.   if ((ci->flags & CCI_L)) n--;
  138.   if (n > 0)
  139.     tr = va_arg(argp, IRRef);
  140.   while (n-- > 1)
  141.     tr = emitir(IRT(IR_CARG, IRT_NIL), tr, va_arg(argp, IRRef));
  142.   va_end(argp);
  143.   if (CCI_OP(ci) == IR_CALLS)
  144.     J->needsnap = 1;  /* Need snapshot after call with side effect. */
  145.   return emitir(CCI_OPTYPE(ci), tr, id);
  146. }

  148. /* -- Interning of constants ---------------------------------------------- */

  150. /*
  151. ** IR instructions for constants are kept between J->cur.nk >= ref < REF_BIAS.
  152. ** They are chained like all other instructions, but grow downwards.
  153. ** The are interned (like strings in the VM) to facilitate reference
  154. ** comparisons. The same constant must get the same reference.
  155. */

  157. /* Get ref of next IR constant and optionally grow IR.
  158. ** Note: this may invalidate all IRIns *!
  159. */
  160. ‌static LJ_AINLINE IRRef ir_nextk(jit_State *J)
  161. {
  162.   IRRef ref = J->cur.nk;
  163.   if (LJ_UNLIKELY(ref <= J->irbotlim)) lj_ir_growbot(J);
  164.   J->cur.nk = --ref;
  165.   return ref;
  166. }

  168. /* Intern int32_t constant. */
  169. ‌TRef LJ_FASTCALL lj_ir_kint(jit_State *J, int32_t k)
  170. {
  171.   IRIns *ir, *cir = J->cur.ir;
  172.   IRRef ref;
  173.   for (ref = J->chain[IR_KINT]; ref; ref = cir[ref].prev)
  174.     if (cir[ref].i == k)
  175.       goto found;
  176.   ref = ir_nextk(J);
  177.   ir = IR(ref);
  178.   ir->i = k;
  179.   ir->t.irt = IRT_INT;
  180.   ir->o = IR_KINT;
  181.   ir->prev = J->chain[IR_KINT];
  182.   J->chain[IR_KINT] = (IRRef1)ref;
  183. found:
  184.   return TREF(ref, IRT_INT);
  185. }

  187. /* The MRef inside the KNUM/KINT64 IR instructions holds the address of the
  188. ** 64 bit constant. The constants themselves are stored in a chained array
  189. ** and shared across traces.
  190. **
  191. ** Rationale for choosing this data structure:
  192. ** - The address of the constants is embedded in the generated machine code
  193. **   and must never move. A resizable array or hash table wouldn't work.
  194. ** - Most apps need very few non-32 bit integer constants (less than a dozen).
  195. ** - Linear search is hard to beat in terms of speed and low complexity.
  196. */
  197. ‌typedef struct K64Array {
  198.   MRef next;                        /* Pointer to next list. */
  199.   MSize numk;                        /* Number of used elements in this array. */
  200.   TValue k[LJ_MIN_K64SZ];        /* Array of constants. */
  201. ‌} K64Array;

  203. /* Free all chained arrays. */
  204. ‌void lj_ir_k64_freeall(jit_State *J)
  205. {
  206.   K64Array *k;
  207.   for (k = mref(J->k64, K64Array); k; ) {
  208.     K64Array *next = mref(k->next, K64Array);
  209.     lj_mem_free(J2G(J), k, sizeof(K64Array));
  210.     k = next;
  211.   }
  212. }

  214. /* Find 64 bit constant in chained array or add it. */
  215. ‌cTValue *lj_ir_k64_find(jit_State *J, uint64_t u64)
  216. {
  217.   K64Array *k, *kp = NULL;
  218.   TValue *ntv;
  219.   MSize idx;
  220.   /* Search for the constant in the whole chain of arrays. */
  221.   for (k = mref(J->k64, K64Array); k; k = mref(k->next, K64Array)) {
  222.     kp = k;  /* Remember previous element in list. */
  223.     for (idx = 0; idx < k->numk; idx++) {  /* Search one array. */
  224.       TValue *tv = &k->k[idx];
  225.       if (tv->u64 == u64)  /* Needed for +-0/NaN/absmask. */
  226.         return tv;
  227.     }
  228.   }
  229.   /* Constant was not found, need to add it. */
  230.   if (!(kp && kp->numk < LJ_MIN_K64SZ)) {  /* Allocate a new array. */
  231.     K64Array *kn = lj_mem_newt(J->L, sizeof(K64Array), K64Array);
  232.     setmref(kn->next, NULL);
  233.     kn->numk = 0;
  234.     if (kp)
  235.       setmref(kp->next, kn);  /* Chain to the end of the list. */
  236.     else
  237.       setmref(J->k64, kn);  /* Link first array. */
  238.     kp = kn;
  239.   }
  240.   ntv = &kp->k[kp->numk++];  /* Add to current array. */
  241.   ntv->u64 = u64;
  242.   return ntv;
  243. }

  245. /* Intern 64 bit constant, given by its address. */
  246. ‌TRef lj_ir_k64(jit_State *J, IROp op, cTValue *tv)
  247. {
  248.   IRIns *ir, *cir = J->cur.ir;
  249.   IRRef ref;
  250.   IRType t = op == IR_KNUM ? IRT_NUM : IRT_I64;
  251.   for (ref = J->chain[op]; ref; ref = cir[ref].prev)
  252.     if (ir_k64(&cir[ref]) == tv)
  253.       goto found;
  254.   ref = ir_nextk(J);
  255.   ir = IR(ref);
  256.   lua_assert(checkptrGC(tv));
  257.   setmref(ir->ptr, tv);
  258.   ir->t.irt = t;
  259.   ir->o = op;
  260.   ir->prev = J->chain[op];
  261.   J->chain[op] = (IRRef1)ref;
  262. found:
  263.   return TREF(ref, t);
  264. }

  266. /* Intern FP constant, given by its 64 bit pattern. */
  267. ‌TRef lj_ir_knum_u64(jit_State *J, uint64_t u64)
  268. {
  269.   return lj_ir_k64(J, IR_KNUM, lj_ir_k64_find(J, u64));
  270. }

  272. /* Intern 64 bit integer constant. */
  273. ‌TRef lj_ir_kint64(jit_State *J, uint64_t u64)
  274. {
  275.   return lj_ir_k64(J, IR_KINT64, lj_ir_k64_find(J, u64));
  276. }

  278. /* Check whether a number is int and return it. -0 is NOT considered an int. */
  279. ‌static int numistrueint(lua_Number n, int32_t *kp)
  280. {
  281.   int32_t k = lj_num2int(n);
  282.   if (n == (lua_Number)k) {
  283.     if (kp) *kp = k;
  284.     if (k == 0) {  /* Special check for -0. */
  285.       TValue tv;
  286.       setnumV(&tv, n);
  287.       if (tv.u32.hi != 0)
  288.         return 0;
  289.     }
  290.     return 1;
  291.   }
  292.   return 0;
  293. }

  295. /* Intern number as int32_t constant if possible, otherwise as FP constant. */
  296. ‌TRef lj_ir_knumint(jit_State *J, lua_Number n)
  297. {
  298.   int32_t k;
  299.   if (numistrueint(n, &k))
  300.     return lj_ir_kint(J, k);
  301.   else
  302.     return lj_ir_knum(J, n);
  303. }

  305. /* Intern GC object "constant". */
  306. ‌TRef lj_ir_kgc(jit_State *J, GCobj *o, IRType t)
  307. {
  308.   IRIns *ir, *cir = J->cur.ir;
  309.   IRRef ref;
  310.   lua_assert(!LJ_GC64);  /* TODO_GC64: major changes required. */
  311.   lua_assert(!isdead(J2G(J), o));
  312.   for (ref = J->chain[IR_KGC]; ref; ref = cir[ref].prev)
  313.     if (ir_kgc(&cir[ref]) == o)
  314.       goto found;
  315.   ref = ir_nextk(J);
  316.   ir = IR(ref);
  317.   /* NOBARRIER: Current trace is a GC root. */
  318.   setgcref(ir->gcr, o);
  319.   ir->t.irt = (uint8_t)t;
  320.   ir->o = IR_KGC;
  321.   ir->prev = J->chain[IR_KGC];
  322.   J->chain[IR_KGC] = (IRRef1)ref;
  323. found:
  324.   return TREF(ref, t);
  325. }

  327. /* Intern 32 bit pointer constant. */
  328. ‌TRef lj_ir_kptr_(jit_State *J, IROp op, void *ptr)
  329. {
  330.   IRIns *ir, *cir = J->cur.ir;
  331.   IRRef ref;
  332.   lua_assert((void *)(intptr_t)i32ptr(ptr) == ptr);
  333.   for (ref = J->chain[op]; ref; ref = cir[ref].prev)
  334.     if (mref(cir[ref].ptr, void) == ptr)
  335.       goto found;
  336.   ref = ir_nextk(J);
  337.   ir = IR(ref);
  338.   setmref(ir->ptr, ptr);
  339.   ir->t.irt = IRT_P32;
  340.   ir->o = op;
  341.   ir->prev = J->chain[op];
  342.   J->chain[op] = (IRRef1)ref;
  343. found:
  344.   return TREF(ref, IRT_P32);
  345. }

  347. /* Intern typed NULL constant. */
  348. ‌TRef lj_ir_knull(jit_State *J, IRType t)
  349. {
  350.   IRIns *ir, *cir = J->cur.ir;
  351.   IRRef ref;
  352.   for (ref = J->chain[IR_KNULL]; ref; ref = cir[ref].prev)
  353.     if (irt_t(cir[ref].t) == t)
  354.       goto found;
  355.   ref = ir_nextk(J);
  356.   ir = IR(ref);
  357.   ir->i = 0;
  358.   ir->t.irt = (uint8_t)t;
  359.   ir->o = IR_KNULL;
  360.   ir->prev = J->chain[IR_KNULL];
  361.   J->chain[IR_KNULL] = (IRRef1)ref;
  362. found:
  363.   return TREF(ref, t);
  364. }

  366. /* Intern key slot. */
  367. ‌TRef lj_ir_kslot(jit_State *J, TRef key, IRRef slot)
  368. {
  369.   IRIns *ir, *cir = J->cur.ir;
  370.   IRRef2 op12 = IRREF2((IRRef1)key, (IRRef1)slot);
  371.   IRRef ref;
  372.   /* Const part is not touched by CSE/DCE, so 0-65535 is ok for IRMlit here. */
  373.   lua_assert(tref_isk(key) && slot == (IRRef)(IRRef1)slot);
  374.   for (ref = J->chain[IR_KSLOT]; ref; ref = cir[ref].prev)
  375.     if (cir[ref].op12 == op12)
  376.       goto found;
  377.   ref = ir_nextk(J);
  378.   ir = IR(ref);
  379.   ir->op12 = op12;
  380.   ir->t.irt = IRT_P32;
  381.   ir->o = IR_KSLOT;
  382.   ir->prev = J->chain[IR_KSLOT];
  383.   J->chain[IR_KSLOT] = (IRRef1)ref;
  384. found:
  385.   return TREF(ref, IRT_P32);
  386. }

  388. /* -- Access to IR constants ---------------------------------------------- */

  390. /* Copy value of IR constant. */
  391. ‌void lj_ir_kvalue(lua_State *L, TValue *tv, const IRIns *ir)
  392. {
  393.   UNUSED(L);
  394.   lua_assert(ir->o != IR_KSLOT);  /* Common mistake. */
  395.   switch (ir->o) {
  396.   case IR_KPRI: setpriV(tv, irt_toitype(ir->t)); break;
  397.   case IR_KINT: setintV(tv, ir->i); break;
  398.   case IR_KGC: setgcV(L, tv, ir_kgc(ir), irt_toitype(ir->t)); break;
  399.   case IR_KPTR: case IR_KKPTR: case IR_KNULL:
  400.     setlightudV(tv, mref(ir->ptr, void));
  401.     break;
  402.   case IR_KNUM: setnumV(tv, ir_knum(ir)->n); break;
  403. #if LJ_HASFFI
  404.   case IR_KINT64: {
  405.     GCcdata *cd = lj_cdata_new_(L, CTID_INT64, 8);
  406.     *(uint64_t *)cdataptr(cd) = ir_kint64(ir)->u64;
  407.     setcdataV(L, tv, cd);
  408.     break;
  409.     }
  410. #endif
  411.   default: lua_assert(0); break;
  412.   }
  413. }

  415. /* -- Convert IR operand types -------------------------------------------- */

  417. /* Convert from string to number. */
  418. ‌TRef LJ_FASTCALL lj_ir_tonumber(jit_State *J, TRef tr)
  419. {
  420.   if (!tref_isnumber(tr)) {
  421.     if (tref_isstr(tr))
  422.       tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
  423.     else
  424.       lj_trace_err(J, LJ_TRERR_BADTYPE);
  425.   }
  426.   return tr;
  427. }

  429. /* Convert from integer or string to number. */
  430. ‌TRef LJ_FASTCALL lj_ir_tonum(jit_State *J, TRef tr)
  431. {
  432.   if (!tref_isnum(tr)) {
  433.     if (tref_isinteger(tr))
  434.       tr = emitir(IRTN(IR_CONV), tr, IRCONV_NUM_INT);
  435.     else if (tref_isstr(tr))
  436.       tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
  437.     else
  438.       lj_trace_err(J, LJ_TRERR_BADTYPE);
  439.   }
  440.   return tr;
  441. }

  443. /* Convert from integer or number to string. */
  444. ‌TRef LJ_FASTCALL lj_ir_tostr(jit_State *J, TRef tr)
  445. {
  446.   if (!tref_isstr(tr)) {
  447.     if (!tref_isnumber(tr))
  448.       lj_trace_err(J, LJ_TRERR_BADTYPE);
  449.     tr = emitir(IRT(IR_TOSTR, IRT_STR), tr,
  450.                 tref_isnum(tr) ? IRTOSTR_NUM : IRTOSTR_INT);
  451.   }
  452.   return tr;
  453. }

  455. /* -- Miscellaneous IR ops ------------------------------------------------ */

  457. /* Evaluate numeric comparison. */
  458. ‌int lj_ir_numcmp(lua_Number a, lua_Number b, IROp op)
  459. {
  460.   switch (op) {
  461.   case IR_EQ: return (a == b);
  462.   case IR_NE: return (a != b);
  463.   case IR_LT: return (a < b);
  464.   case IR_GE: return (a >= b);
  465.   case IR_LE: return (a <= b);
  466.   case IR_GT: return (a > b);
  467.   case IR_ULT: return !(a >= b);
  468.   case IR_UGE: return !(a < b);
  469.   case IR_ULE: return !(a > b);
  470.   case IR_UGT: return !(a <= b);
  471.   default: lua_assert(0); return 0;
  472.   }
  473. }

  475. /* Evaluate string comparison. */
  476. ‌int lj_ir_strcmp(GCstr *a, GCstr *b, IROp op)
  477. {
  478.   int res = lj_str_cmp(a, b);
  479.   switch (op) {
  480.   case IR_LT: return (res < 0);
  481.   case IR_GE: return (res >= 0);
  482.   case IR_LE: return (res <= 0);
  483.   case IR_GT: return (res > 0);
  484.   default: lua_assert(0); return 0;
  485.   }
  486. }

  488. /* Rollback IR to previous state. */
  489. ‌void lj_ir_rollback(jit_State *J, IRRef ref)
  490. {
  491.   IRRef nins = J->cur.nins;
  492.   while (nins > ref) {
  493.     IRIns *ir;
  494.     nins--;
  495.     ir = IR(nins);
  496.     J->chain[ir->o] = ir->prev;
  497.   }
  498.   J->cur.nins = nins;
  499. }

  501. ‌#undef IR
  502. ‌#undef fins
  503. ‌#undef emitir

  505. #endif

One Level Up Top Level