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