src/lj_ir.c

   1 /*
   2 ** SSA IR (Intermediate Representation) emitter.
   3 ** Copyright (C) 2005-2023 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_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_serialize.h"
  34 #include "lj_strfmt.h"
  35 #include "lj_prng.h"
  36
  37 /* Some local macros to save typing. Undef'd at the end. */
  38 #define IR(ref)                 (&J->cur.ir[(ref)])
  39 #define fins                    (&J->fold.ins)
  40
  41 /* Pass IR on to next optimization in chain (FOLD). */
  42 #define emitir(ot, a, b)        (lj_ir_set(J, (ot), (a), (b)), lj_opt_fold(J))
  43
  44 /* -- IR tables ----------------------------------------------------------- */
  45
  46 /* IR instruction modes. */
  47 LJ_DATADEF const uint8_t lj_ir_mode[IR__MAX+1] = {
  48 IRDEF(IRMODE)
  49   0
  50 };
  51
  52 /* IR type sizes. */
  53 LJ_DATADEF const uint8_t lj_ir_type_size[IRT__MAX+1] = {
  54 #define IRTSIZE(name, size)     size,
  55 IRTDEF(IRTSIZE)
  56 #undef IRTSIZE
  57   0
  58 };
  59
  60 /* C call info for CALL* instructions. */
  61 LJ_DATADEF const CCallInfo lj_ir_callinfo[] = {
  62 #define IRCALLCI(cond, name, nargs, kind, type, flags) \
  63   { (ASMFunction)IRCALLCOND_##cond(name), \
  64     (nargs)|(CCI_CALL_##kind)|(IRT_##type<<CCI_OTSHIFT)|(flags) },
  65 IRCALLDEF(IRCALLCI)
  66 #undef IRCALLCI
  67   { NULL, 0 }
  68 };
  69
  70 /* -- IR emitter ---------------------------------------------------------- */
  71
  72 /* Grow IR buffer at the top. */
  73 void LJ_FASTCALL lj_ir_growtop(jit_State *J)
  74 {
  75   IRIns *baseir = J->irbuf + J->irbotlim;
  76   MSize szins = J->irtoplim - J->irbotlim;
  77   if (szins) {
  78     baseir = (IRIns *)lj_mem_realloc(J->L, baseir, szins*sizeof(IRIns),
  79                                      2*szins*sizeof(IRIns));
  80     J->irtoplim = J->irbotlim + 2*szins;
  81   } else {
  82     baseir = (IRIns *)lj_mem_realloc(J->L, NULL, 0, LJ_MIN_IRSZ*sizeof(IRIns));
  83     J->irbotlim = REF_BASE - LJ_MIN_IRSZ/4;
  84     J->irtoplim = J->irbotlim + LJ_MIN_IRSZ;
  85   }
  86   J->cur.ir = J->irbuf = baseir - J->irbotlim;
  87 }
  88
  89 /* Grow IR buffer at the bottom or shift it up. */
  90 static void lj_ir_growbot(jit_State *J)
  91 {
  92   IRIns *baseir = J->irbuf + J->irbotlim;
  93   MSize szins = J->irtoplim - J->irbotlim;
  94   lj_assertJ(szins != 0, "zero IR size");
  95   lj_assertJ(J->cur.nk == J->irbotlim || J->cur.nk-1 == J->irbotlim,
  96              "unexpected IR growth");
  97   if (J->cur.nins + (szins >> 1) < J->irtoplim) {
  98     /* More than half of the buffer is free on top: shift up by a quarter. */
  99     MSize ofs = szins >> 2;
 100     memmove(baseir + ofs, baseir, (J->cur.nins - J->irbotlim)*sizeof(IRIns));
 101     J->irbotlim -= ofs;
 102     J->irtoplim -= ofs;
 103     J->cur.ir = J->irbuf = baseir - J->irbotlim;
 104   } else {
 105     /* Double the buffer size, but split the growth amongst top/bottom. */
 106     IRIns *newbase = lj_mem_newt(J->L, 2*szins*sizeof(IRIns), IRIns);
 107     MSize ofs = szins >= 256 ? 128 : (szins >> 1);  /* Limit bottom growth. */
 108     memcpy(newbase + ofs, baseir, (J->cur.nins - J->irbotlim)*sizeof(IRIns));
 109     lj_mem_free(G(J->L), baseir, szins*sizeof(IRIns));
 110     J->irbotlim -= ofs;
 111     J->irtoplim = J->irbotlim + 2*szins;
 112     J->cur.ir = J->irbuf = newbase - J->irbotlim;
 113   }
 114 }
 115
 116 /* Emit IR without any optimizations. */
 117 TRef LJ_FASTCALL lj_ir_emit(jit_State *J)
 118 {
 119   IRRef ref = lj_ir_nextins(J);
 120   IRIns *ir = IR(ref);
 121   IROp op = fins->o;
 122   ir->prev = J->chain[op];
 123   J->chain[op] = (IRRef1)ref;
 124   ir->o = op;
 125   ir->op1 = fins->op1;
 126   ir->op2 = fins->op2;
 127   J->guardemit.irt |= fins->t.irt;
 128   return TREF(ref, irt_t((ir->t = fins->t)));
 129 }
 130
 131 /* Emit call to a C function. */
 132 TRef lj_ir_call(jit_State *J, IRCallID id, ...)
 133 {
 134   const CCallInfo *ci = &lj_ir_callinfo[id];
 135   uint32_t n = CCI_NARGS(ci);
 136   TRef tr = TREF_NIL;
 137   va_list argp;
 138   va_start(argp, id);
 139   if ((ci->flags & CCI_L)) n--;
 140   if (n > 0)
 141     tr = va_arg(argp, IRRef);
 142   while (n-- > 1)
 143     tr = emitir(IRT(IR_CARG, IRT_NIL), tr, va_arg(argp, IRRef));
 144   va_end(argp);
 145   if (CCI_OP(ci) == IR_CALLS)
 146     J->needsnap = 1;  /* Need snapshot after call with side effect. */
 147   return emitir(CCI_OPTYPE(ci), tr, id);
 148 }
 149
 150 /* Load field of type t from GG_State + offset. Must be 32 bit aligned. */
 151 TRef lj_ir_ggfload(jit_State *J, IRType t, uintptr_t ofs)
 152 {
 153   lj_assertJ((ofs & 3) == 0, "unaligned GG_State field offset");
 154   ofs >>= 2;
 155   lj_assertJ(ofs >= IRFL__MAX && ofs <= 0x3ff,
 156              "GG_State field offset breaks 10 bit FOLD key limit");
 157   lj_ir_set(J, IRT(IR_FLOAD, t), REF_NIL, ofs);
 158   return lj_opt_fold(J);
 159 }
 160
 161 /* -- Interning of constants ---------------------------------------------- */
 162
 163 /*
 164 ** IR instructions for constants are kept between J->cur.nk >= ref < REF_BIAS.
 165 ** They are chained like all other instructions, but grow downwards.
 166 ** The are interned (like strings in the VM) to facilitate reference
 167 ** comparisons. The same constant must get the same reference.
 168 */
 169
 170 /* Get ref of next IR constant and optionally grow IR.
 171 ** Note: this may invalidate all IRIns *!
 172 */
 173 static LJ_AINLINE IRRef ir_nextk(jit_State *J)
 174 {
 175   IRRef ref = J->cur.nk;
 176   if (LJ_UNLIKELY(ref <= J->irbotlim)) lj_ir_growbot(J);
 177   J->cur.nk = --ref;
 178   return ref;
 179 }
 180
 181 /* Get ref of next 64 bit IR constant and optionally grow IR.
 182 ** Note: this may invalidate all IRIns *!
 183 */
 184 static LJ_AINLINE IRRef ir_nextk64(jit_State *J)
 185 {
 186   IRRef ref = J->cur.nk - 2;
 187   lj_assertJ(J->state != LJ_TRACE_ASM, "bad JIT state");
 188   if (LJ_UNLIKELY(ref < J->irbotlim)) lj_ir_growbot(J);
 189   J->cur.nk = ref;
 190   return ref;
 191 }
 192
 193 #if LJ_GC64
 194 #define ir_nextkgc ir_nextk64
 195 #else
 196 #define ir_nextkgc ir_nextk
 197 #endif
 198
 199 /* Intern int32_t constant. */
 200 TRef LJ_FASTCALL lj_ir_kint(jit_State *J, int32_t k)
 201 {
 202   IRIns *ir, *cir = J->cur.ir;
 203   IRRef ref;
 204   for (ref = J->chain[IR_KINT]; ref; ref = cir[ref].prev)
 205     if (cir[ref].i == k)
 206       goto found;
 207   ref = ir_nextk(J);
 208   ir = IR(ref);
 209   ir->i = k;
 210   ir->t.irt = IRT_INT;
 211   ir->o = IR_KINT;
 212   ir->prev = J->chain[IR_KINT];
 213   J->chain[IR_KINT] = (IRRef1)ref;
 214 found:
 215   return TREF(ref, IRT_INT);
 216 }
 217
 218 /* Intern 64 bit constant, given by its 64 bit pattern. */
 219 TRef lj_ir_k64(jit_State *J, IROp op, uint64_t u64)
 220 {
 221   IRIns *ir, *cir = J->cur.ir;
 222   IRRef ref;
 223   IRType t = op == IR_KNUM ? IRT_NUM : IRT_I64;
 224   for (ref = J->chain[op]; ref; ref = cir[ref].prev)
 225     if (ir_k64(&cir[ref])->u64 == u64)
 226       goto found;
 227   ref = ir_nextk64(J);
 228   ir = IR(ref);
 229   ir[1].tv.u64 = u64;
 230   ir->t.irt = t;
 231   ir->o = op;
 232   ir->op12 = 0;
 233   ir->prev = J->chain[op];
 234   J->chain[op] = (IRRef1)ref;
 235 found:
 236   return TREF(ref, t);
 237 }
 238
 239 /* Intern FP constant, given by its 64 bit pattern. */
 240 TRef lj_ir_knum_u64(jit_State *J, uint64_t u64)
 241 {
 242   return lj_ir_k64(J, IR_KNUM, u64);
 243 }
 244
 245 /* Intern 64 bit integer constant. */
 246 TRef lj_ir_kint64(jit_State *J, uint64_t u64)
 247 {
 248   return lj_ir_k64(J, IR_KINT64, u64);
 249 }
 250
 251 /* Check whether a number is int and return it. -0 is NOT considered an int. */
 252 static int numistrueint(lua_Number n, int32_t *kp)
 253 {
 254   int32_t k = lj_num2int(n);
 255   if (n == (lua_Number)k) {
 256     if (kp) *kp = k;
 257     if (k == 0) {  /* Special check for -0. */
 258       TValue tv;
 259       setnumV(&tv, n);
 260       if (tv.u32.hi != 0)
 261         return 0;
 262     }
 263     return 1;
 264   }
 265   return 0;
 266 }
 267
 268 /* Intern number as int32_t constant if possible, otherwise as FP constant. */
 269 TRef lj_ir_knumint(jit_State *J, lua_Number n)
 270 {
 271   int32_t k;
 272   if (numistrueint(n, &k))
 273     return lj_ir_kint(J, k);
 274   else
 275     return lj_ir_knum(J, n);
 276 }
 277
 278 /* Intern GC object "constant". */
 279 TRef lj_ir_kgc(jit_State *J, GCobj *o, IRType t)
 280 {
 281   IRIns *ir, *cir = J->cur.ir;
 282   IRRef ref;
 283   lj_assertJ(!isdead(J2G(J), o), "interning of dead GC object");
 284   for (ref = J->chain[IR_KGC]; ref; ref = cir[ref].prev)
 285     if (ir_kgc(&cir[ref]) == o)
 286       goto found;
 287   ref = ir_nextkgc(J);
 288   ir = IR(ref);
 289   /* NOBARRIER: Current trace is a GC root. */
 290   ir->op12 = 0;
 291   setgcref(ir[LJ_GC64].gcr, o);
 292   ir->t.irt = (uint8_t)t;
 293   ir->o = IR_KGC;
 294   ir->prev = J->chain[IR_KGC];
 295   J->chain[IR_KGC] = (IRRef1)ref;
 296 found:
 297   return TREF(ref, t);
 298 }
 299
 300 /* Allocate GCtrace constant placeholder (no interning). */
 301 TRef lj_ir_ktrace(jit_State *J)
 302 {
 303   IRRef ref = ir_nextkgc(J);
 304   IRIns *ir = IR(ref);
 305   lj_assertJ(irt_toitype_(IRT_P64) == LJ_TTRACE, "mismatched type mapping");
 306   ir->t.irt = IRT_P64;
 307   ir->o = LJ_GC64 ? IR_KNUM : IR_KNULL;  /* Not IR_KGC yet, but same size. */
 308   ir->op12 = 0;
 309   ir->prev = 0;
 310   return TREF(ref, IRT_P64);
 311 }
 312
 313 /* Intern 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 #if LJ_64 && !LJ_GC64
 319   lj_assertJ((void *)(uintptr_t)u32ptr(ptr) == ptr, "out-of-range GC pointer");
 320 #endif
 321   for (ref = J->chain[op]; ref; ref = cir[ref].prev)
 322     if (ir_kptr(&cir[ref]) == ptr)
 323       goto found;
 324 #if LJ_GC64
 325   ref = ir_nextk64(J);
 326 #else
 327   ref = ir_nextk(J);
 328 #endif
 329   ir = IR(ref);
 330   ir->op12 = 0;
 331   setmref(ir[LJ_GC64].ptr, ptr);
 332   ir->t.irt = IRT_PGC;
 333   ir->o = op;
 334   ir->prev = J->chain[op];
 335   J->chain[op] = (IRRef1)ref;
 336 found:
 337   return TREF(ref, IRT_PGC);
 338 }
 339
 340 /* Intern typed NULL constant. */
 341 TRef lj_ir_knull(jit_State *J, IRType t)
 342 {
 343   IRIns *ir, *cir = J->cur.ir;
 344   IRRef ref;
 345   for (ref = J->chain[IR_KNULL]; ref; ref = cir[ref].prev)
 346     if (irt_t(cir[ref].t) == t)
 347       goto found;
 348   ref = ir_nextk(J);
 349   ir = IR(ref);
 350   ir->i = 0;
 351   ir->t.irt = (uint8_t)t;
 352   ir->o = IR_KNULL;
 353   ir->prev = J->chain[IR_KNULL];
 354   J->chain[IR_KNULL] = (IRRef1)ref;
 355 found:
 356   return TREF(ref, t);
 357 }
 358
 359 /* Intern key slot. */
 360 TRef lj_ir_kslot(jit_State *J, TRef key, IRRef slot)
 361 {
 362   IRIns *ir, *cir = J->cur.ir;
 363   IRRef2 op12 = IRREF2((IRRef1)key, (IRRef1)slot);
 364   IRRef ref;
 365   /* Const part is not touched by CSE/DCE, so 0-65535 is ok for IRMlit here. */
 366   lj_assertJ(tref_isk(key) && slot == (IRRef)(IRRef1)slot,
 367              "out-of-range key/slot");
 368   for (ref = J->chain[IR_KSLOT]; ref; ref = cir[ref].prev)
 369     if (cir[ref].op12 == op12)
 370       goto found;
 371   ref = ir_nextk(J);
 372   ir = IR(ref);
 373   ir->op12 = op12;
 374   ir->t.irt = IRT_P32;
 375   ir->o = IR_KSLOT;
 376   ir->prev = J->chain[IR_KSLOT];
 377   J->chain[IR_KSLOT] = (IRRef1)ref;
 378 found:
 379   return TREF(ref, IRT_P32);
 380 }
 381
 382 /* -- Access to IR constants ---------------------------------------------- */
 383
 384 /* Copy value of IR constant. */
 385 void lj_ir_kvalue(lua_State *L, TValue *tv, const IRIns *ir)
 386 {
 387   UNUSED(L);
 388   lj_assertL(ir->o != IR_KSLOT, "unexpected KSLOT");  /* Common mistake. */
 389   switch (ir->o) {
 390   case IR_KPRI: setpriV(tv, irt_toitype(ir->t)); break;
 391   case IR_KINT: setintV(tv, ir->i); break;
 392   case IR_KGC: setgcV(L, tv, ir_kgc(ir), irt_toitype(ir->t)); break;
 393   case IR_KPTR: case IR_KKPTR:
 394     setnumV(tv, (lua_Number)(uintptr_t)ir_kptr(ir));
 395     break;
 396   case IR_KNULL: setintV(tv, 0); break;
 397   case IR_KNUM: setnumV(tv, ir_knum(ir)->n); break;
 398 #if LJ_HASFFI
 399   case IR_KINT64: {
 400     GCcdata *cd = lj_cdata_new_(L, CTID_INT64, 8);
 401     *(uint64_t *)cdataptr(cd) = ir_kint64(ir)->u64;
 402     setcdataV(L, tv, cd);
 403     break;
 404     }
 405 #endif
 406   default: lj_assertL(0, "bad IR constant op %d", ir->o); break;
 407   }
 408 }
 409
 410 /* -- Convert IR operand types -------------------------------------------- */
 411
 412 /* Convert from string to number. */
 413 TRef LJ_FASTCALL lj_ir_tonumber(jit_State *J, TRef tr)
 414 {
 415   if (!tref_isnumber(tr)) {
 416     if (tref_isstr(tr))
 417       tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
 418     else
 419       lj_trace_err(J, LJ_TRERR_BADTYPE);
 420   }
 421   return tr;
 422 }
 423
 424 /* Convert from integer or string to number. */
 425 TRef LJ_FASTCALL lj_ir_tonum(jit_State *J, TRef tr)
 426 {
 427   if (!tref_isnum(tr)) {
 428     if (tref_isinteger(tr))
 429       tr = emitir(IRTN(IR_CONV), tr, IRCONV_NUM_INT);
 430     else if (tref_isstr(tr))
 431       tr = emitir(IRTG(IR_STRTO, IRT_NUM), tr, 0);
 432     else
 433       lj_trace_err(J, LJ_TRERR_BADTYPE);
 434   }
 435   return tr;
 436 }
 437
 438 /* Convert from integer or number to string. */
 439 TRef LJ_FASTCALL lj_ir_tostr(jit_State *J, TRef tr)
 440 {
 441   if (!tref_isstr(tr)) {
 442     if (!tref_isnumber(tr))
 443       lj_trace_err(J, LJ_TRERR_BADTYPE);
 444     tr = emitir(IRT(IR_TOSTR, IRT_STR), tr,
 445                 tref_isnum(tr) ? IRTOSTR_NUM : IRTOSTR_INT);
 446   }
 447   return tr;
 448 }
 449
 450 /* -- Miscellaneous IR ops ------------------------------------------------ */
 451
 452 /* Evaluate numeric comparison. */
 453 int lj_ir_numcmp(lua_Number a, lua_Number b, IROp op)
 454 {
 455   switch (op) {
 456   case IR_EQ: return (a == b);
 457   case IR_NE: return (a != b);
 458   case IR_LT: return (a < b);
 459   case IR_GE: return (a >= b);
 460   case IR_LE: return (a <= b);
 461   case IR_GT: return (a > b);
 462   case IR_ULT: return !(a >= b);
 463   case IR_UGE: return !(a < b);
 464   case IR_ULE: return !(a > b);
 465   case IR_UGT: return !(a <= b);
 466   default: lj_assertX(0, "bad IR op %d", op); return 0;
 467   }
 468 }
 469
 470 /* Evaluate string comparison. */
 471 int lj_ir_strcmp(GCstr *a, GCstr *b, IROp op)
 472 {
 473   int res = lj_str_cmp(a, b);
 474   switch (op) {
 475   case IR_LT: return (res < 0);
 476   case IR_GE: return (res >= 0);
 477   case IR_LE: return (res <= 0);
 478   case IR_GT: return (res > 0);
 479   default: lj_assertX(0, "bad IR op %d", op); return 0;
 480   }
 481 }
 482
 483 /* Rollback IR to previous state. */
 484 void lj_ir_rollback(jit_State *J, IRRef ref)
 485 {
 486   IRRef nins = J->cur.nins;
 487   while (nins > ref) {
 488     IRIns *ir;
 489     nins--;
 490     ir = IR(nins);
 491     J->chain[ir->o] = ir->prev;
 492   }
 493   J->cur.nins = nins;
 494 }
 495
 496 #undef IR
 497 #undef fins
 498 #undef emitir
 499
 500 #endif