src/lj_ir.c

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