2 ** SSA IR (Intermediate Representation) emitter.
3 ** Copyright (C) 2005-2015 Mike Pall. See Copyright Notice in luajit.h
9 /* For pointers to libc/libm functions. */
22 #include "lj_ircall.h"
28 #include "lj_carith.h"
31 #include "lj_strscan.h"
34 /* Some local macros to save typing. Undef'd at the end. */
35 #define IR(ref) (&J->cur.ir[(ref)])
36 #define fins (&J->fold.ins)
38 /* Pass IR on to next optimization in chain (FOLD). */
39 #define emitir(ot, a, b) (lj_ir_set(J, (ot), (a), (b)), lj_opt_fold(J))
41 /* -- IR tables ----------------------------------------------------------- */
43 /* IR instruction modes. */
44 LJ_DATADEF
const uint8_t lj_ir_mode
[IR__MAX
+1] = {
50 LJ_DATADEF
const uint8_t lj_ir_type_size
[IRT__MAX
+1] = {
51 #define IRTSIZE(name, size) size,
57 /* C call info for CALL* instructions. */
58 LJ_DATADEF
const CCallInfo lj_ir_callinfo
[] = {
59 #define IRCALLCI(cond, name, nargs, kind, type, flags) \
60 { (ASMFunction)IRCALLCOND_##cond(name), \
61 (nargs)|(CCI_CALL_##kind)|(IRT_##type<<CCI_OTSHIFT)|(flags) },
67 /* -- IR emitter ---------------------------------------------------------- */
69 /* Grow IR buffer at the top. */
70 void LJ_FASTCALL
lj_ir_growtop(jit_State
*J
)
72 IRIns
*baseir
= J
->irbuf
+ J
->irbotlim
;
73 MSize szins
= J
->irtoplim
- J
->irbotlim
;
75 baseir
= (IRIns
*)lj_mem_realloc(J
->L
, baseir
, szins
*sizeof(IRIns
),
76 2*szins
*sizeof(IRIns
));
77 J
->irtoplim
= J
->irbotlim
+ 2*szins
;
79 baseir
= (IRIns
*)lj_mem_realloc(J
->L
, NULL
, 0, LJ_MIN_IRSZ
*sizeof(IRIns
));
80 J
->irbotlim
= REF_BASE
- LJ_MIN_IRSZ
/4;
81 J
->irtoplim
= J
->irbotlim
+ LJ_MIN_IRSZ
;
83 J
->cur
.ir
= J
->irbuf
= baseir
- J
->irbotlim
;
86 /* Grow IR buffer at the bottom or shift it up. */
87 static void lj_ir_growbot(jit_State
*J
)
89 IRIns
*baseir
= J
->irbuf
+ J
->irbotlim
;
90 MSize szins
= J
->irtoplim
- J
->irbotlim
;
91 lua_assert(szins
!= 0);
92 lua_assert(J
->cur
.nk
== J
->irbotlim
);
93 if (J
->cur
.nins
+ (szins
>> 1) < J
->irtoplim
) {
94 /* More than half of the buffer is free on top: shift up by a quarter. */
95 MSize ofs
= szins
>> 2;
96 memmove(baseir
+ ofs
, baseir
, (J
->cur
.nins
- J
->irbotlim
)*sizeof(IRIns
));
99 J
->cur
.ir
= J
->irbuf
= baseir
- J
->irbotlim
;
101 /* Double the buffer size, but split the growth amongst top/bottom. */
102 IRIns
*newbase
= lj_mem_newt(J
->L
, 2*szins
*sizeof(IRIns
), IRIns
);
103 MSize ofs
= szins
>= 256 ? 128 : (szins
>> 1); /* Limit bottom growth. */
104 memcpy(newbase
+ ofs
, baseir
, (J
->cur
.nins
- J
->irbotlim
)*sizeof(IRIns
));
105 lj_mem_free(G(J
->L
), baseir
, szins
*sizeof(IRIns
));
107 J
->irtoplim
= J
->irbotlim
+ 2*szins
;
108 J
->cur
.ir
= J
->irbuf
= newbase
- J
->irbotlim
;
112 /* Emit IR without any optimizations. */
113 TRef LJ_FASTCALL
lj_ir_emit(jit_State
*J
)
115 IRRef ref
= lj_ir_nextins(J
);
118 ir
->prev
= J
->chain
[op
];
119 J
->chain
[op
] = (IRRef1
)ref
;
123 J
->guardemit
.irt
|= fins
->t
.irt
;
124 return TREF(ref
, irt_t((ir
->t
= fins
->t
)));
127 /* Emit call to a C function. */
128 TRef
lj_ir_call(jit_State
*J
, IRCallID id
, ...)
130 const CCallInfo
*ci
= &lj_ir_callinfo
[id
];
131 uint32_t n
= CCI_NARGS(ci
);
135 if ((ci
->flags
& CCI_L
)) n
--;
137 tr
= va_arg(argp
, IRRef
);
139 tr
= emitir(IRT(IR_CARG
, IRT_NIL
), tr
, va_arg(argp
, IRRef
));
141 if (CCI_OP(ci
) == IR_CALLS
)
142 J
->needsnap
= 1; /* Need snapshot after call with side effect. */
143 return emitir(CCI_OPTYPE(ci
), tr
, id
);
146 /* -- Interning of constants ---------------------------------------------- */
149 ** IR instructions for constants are kept between J->cur.nk >= ref < REF_BIAS.
150 ** They are chained like all other instructions, but grow downwards.
151 ** The are interned (like strings in the VM) to facilitate reference
152 ** comparisons. The same constant must get the same reference.
155 /* Get ref of next IR constant and optionally grow IR.
156 ** Note: this may invalidate all IRIns *!
158 static LJ_AINLINE IRRef
ir_nextk(jit_State
*J
)
160 IRRef ref
= J
->cur
.nk
;
161 if (LJ_UNLIKELY(ref
<= J
->irbotlim
)) lj_ir_growbot(J
);
166 /* Intern int32_t constant. */
167 TRef LJ_FASTCALL
lj_ir_kint(jit_State
*J
, int32_t k
)
169 IRIns
*ir
, *cir
= J
->cur
.ir
;
171 for (ref
= J
->chain
[IR_KINT
]; ref
; ref
= cir
[ref
].prev
)
179 ir
->prev
= J
->chain
[IR_KINT
];
180 J
->chain
[IR_KINT
] = (IRRef1
)ref
;
182 return TREF(ref
, IRT_INT
);
185 /* The MRef inside the KNUM/KINT64 IR instructions holds the address of the
186 ** 64 bit constant. The constants themselves are stored in a chained array
187 ** and shared across traces.
189 ** Rationale for choosing this data structure:
190 ** - The address of the constants is embedded in the generated machine code
191 ** and must never move. A resizable array or hash table wouldn't work.
192 ** - Most apps need very few non-32 bit integer constants (less than a dozen).
193 ** - Linear search is hard to beat in terms of speed and low complexity.
195 typedef struct K64Array
{
196 MRef next
; /* Pointer to next list. */
197 MSize numk
; /* Number of used elements in this array. */
198 TValue k
[LJ_MIN_K64SZ
]; /* Array of constants. */
201 /* Free all chained arrays. */
202 void lj_ir_k64_freeall(jit_State
*J
)
205 for (k
= mref(J
->k64
, K64Array
); k
; ) {
206 K64Array
*next
= mref(k
->next
, K64Array
);
207 lj_mem_free(J2G(J
), k
, sizeof(K64Array
));
212 /* Find 64 bit constant in chained array or add it. */
213 cTValue
*lj_ir_k64_find(jit_State
*J
, uint64_t u64
)
215 K64Array
*k
, *kp
= NULL
;
218 /* Search for the constant in the whole chain of arrays. */
219 for (k
= mref(J
->k64
, K64Array
); k
; k
= mref(k
->next
, K64Array
)) {
220 kp
= k
; /* Remember previous element in list. */
221 for (idx
= 0; idx
< k
->numk
; idx
++) { /* Search one array. */
222 TValue
*tv
= &k
->k
[idx
];
223 if (tv
->u64
== u64
) /* Needed for +-0/NaN/absmask. */
227 /* Constant was not found, need to add it. */
228 if (!(kp
&& kp
->numk
< LJ_MIN_K64SZ
)) { /* Allocate a new array. */
229 K64Array
*kn
= lj_mem_newt(J
->L
, sizeof(K64Array
), K64Array
);
230 setmref(kn
->next
, NULL
);
233 setmref(kp
->next
, kn
); /* Chain to the end of the list. */
235 setmref(J
->k64
, kn
); /* Link first array. */
238 ntv
= &kp
->k
[kp
->numk
++]; /* Add to current array. */
243 /* Intern 64 bit constant, given by its address. */
244 TRef
lj_ir_k64(jit_State
*J
, IROp op
, cTValue
*tv
)
246 IRIns
*ir
, *cir
= J
->cur
.ir
;
248 IRType t
= op
== IR_KNUM
? IRT_NUM
: IRT_I64
;
249 for (ref
= J
->chain
[op
]; ref
; ref
= cir
[ref
].prev
)
250 if (ir_k64(&cir
[ref
]) == tv
)
254 lua_assert(checkptr32(tv
));
255 setmref(ir
->ptr
, tv
);
258 ir
->prev
= J
->chain
[op
];
259 J
->chain
[op
] = (IRRef1
)ref
;
264 /* Intern FP constant, given by its 64 bit pattern. */
265 TRef
lj_ir_knum_u64(jit_State
*J
, uint64_t u64
)
267 return lj_ir_k64(J
, IR_KNUM
, lj_ir_k64_find(J
, u64
));
270 /* Intern 64 bit integer constant. */
271 TRef
lj_ir_kint64(jit_State
*J
, uint64_t u64
)
273 return lj_ir_k64(J
, IR_KINT64
, lj_ir_k64_find(J
, u64
));
276 /* Check whether a number is int and return it. -0 is NOT considered an int. */
277 static int numistrueint(lua_Number n
, int32_t *kp
)
279 int32_t k
= lj_num2int(n
);
280 if (n
== (lua_Number
)k
) {
282 if (k
== 0) { /* Special check for -0. */
293 /* Intern number as int32_t constant if possible, otherwise as FP constant. */
294 TRef
lj_ir_knumint(jit_State
*J
, lua_Number n
)
297 if (numistrueint(n
, &k
))
298 return lj_ir_kint(J
, k
);
300 return lj_ir_knum(J
, n
);
303 /* Intern GC object "constant". */
304 TRef
lj_ir_kgc(jit_State
*J
, GCobj
*o
, IRType t
)
306 IRIns
*ir
, *cir
= J
->cur
.ir
;
308 lua_assert(!isdead(J2G(J
), o
));
309 for (ref
= J
->chain
[IR_KGC
]; ref
; ref
= cir
[ref
].prev
)
310 if (ir_kgc(&cir
[ref
]) == o
)
314 /* NOBARRIER: Current trace is a GC root. */
315 setgcref(ir
->gcr
, o
);
316 ir
->t
.irt
= (uint8_t)t
;
318 ir
->prev
= J
->chain
[IR_KGC
];
319 J
->chain
[IR_KGC
] = (IRRef1
)ref
;
324 /* Intern 32 bit pointer constant. */
325 TRef
lj_ir_kptr_(jit_State
*J
, IROp op
, void *ptr
)
327 IRIns
*ir
, *cir
= J
->cur
.ir
;
329 lua_assert((void *)(intptr_t)i32ptr(ptr
) == ptr
);
330 for (ref
= J
->chain
[op
]; ref
; ref
= cir
[ref
].prev
)
331 if (mref(cir
[ref
].ptr
, void) == ptr
)
335 setmref(ir
->ptr
, ptr
);
338 ir
->prev
= J
->chain
[op
];
339 J
->chain
[op
] = (IRRef1
)ref
;
341 return TREF(ref
, IRT_P32
);
344 /* Intern typed NULL constant. */
345 TRef
lj_ir_knull(jit_State
*J
, IRType t
)
347 IRIns
*ir
, *cir
= J
->cur
.ir
;
349 for (ref
= J
->chain
[IR_KNULL
]; ref
; ref
= cir
[ref
].prev
)
350 if (irt_t(cir
[ref
].t
) == t
)
355 ir
->t
.irt
= (uint8_t)t
;
357 ir
->prev
= J
->chain
[IR_KNULL
];
358 J
->chain
[IR_KNULL
] = (IRRef1
)ref
;
363 /* Intern key slot. */
364 TRef
lj_ir_kslot(jit_State
*J
, TRef key
, IRRef slot
)
366 IRIns
*ir
, *cir
= J
->cur
.ir
;
367 IRRef2 op12
= IRREF2((IRRef1
)key
, (IRRef1
)slot
);
369 /* Const part is not touched by CSE/DCE, so 0-65535 is ok for IRMlit here. */
370 lua_assert(tref_isk(key
) && slot
== (IRRef
)(IRRef1
)slot
);
371 for (ref
= J
->chain
[IR_KSLOT
]; ref
; ref
= cir
[ref
].prev
)
372 if (cir
[ref
].op12
== op12
)
379 ir
->prev
= J
->chain
[IR_KSLOT
];
380 J
->chain
[IR_KSLOT
] = (IRRef1
)ref
;
382 return TREF(ref
, IRT_P32
);
385 /* -- Access to IR constants ---------------------------------------------- */
387 /* Copy value of IR constant. */
388 void lj_ir_kvalue(lua_State
*L
, TValue
*tv
, const IRIns
*ir
)
391 lua_assert(ir
->o
!= IR_KSLOT
); /* Common mistake. */
393 case IR_KPRI
: setitype(tv
, irt_toitype(ir
->t
)); break;
394 case IR_KINT
: setintV(tv
, ir
->i
); break;
395 case IR_KGC
: setgcV(L
, tv
, ir_kgc(ir
), irt_toitype(ir
->t
)); break;
396 case IR_KPTR
: case IR_KKPTR
: case IR_KNULL
:
397 setlightudV(tv
, mref(ir
->ptr
, void));
399 case IR_KNUM
: setnumV(tv
, ir_knum(ir
)->n
); break;
402 GCcdata
*cd
= lj_cdata_new_(L
, CTID_INT64
, 8);
403 *(uint64_t *)cdataptr(cd
) = ir_kint64(ir
)->u64
;
404 setcdataV(L
, tv
, cd
);
408 default: lua_assert(0); break;
412 /* -- Convert IR operand types -------------------------------------------- */
414 /* Convert from string to number. */
415 TRef LJ_FASTCALL
lj_ir_tonumber(jit_State
*J
, TRef tr
)
417 if (!tref_isnumber(tr
)) {
419 tr
= emitir(IRTG(IR_STRTO
, IRT_NUM
), tr
, 0);
421 lj_trace_err(J
, LJ_TRERR_BADTYPE
);
426 /* Convert from integer or string to number. */
427 TRef LJ_FASTCALL
lj_ir_tonum(jit_State
*J
, TRef tr
)
429 if (!tref_isnum(tr
)) {
430 if (tref_isinteger(tr
))
431 tr
= emitir(IRTN(IR_CONV
), tr
, IRCONV_NUM_INT
);
432 else if (tref_isstr(tr
))
433 tr
= emitir(IRTG(IR_STRTO
, IRT_NUM
), tr
, 0);
435 lj_trace_err(J
, LJ_TRERR_BADTYPE
);
440 /* Convert from integer or number to string. */
441 TRef LJ_FASTCALL
lj_ir_tostr(jit_State
*J
, TRef tr
)
443 if (!tref_isstr(tr
)) {
444 if (!tref_isnumber(tr
))
445 lj_trace_err(J
, LJ_TRERR_BADTYPE
);
446 tr
= emitir(IRT(IR_TOSTR
, IRT_STR
), tr
, 0);
451 /* -- Miscellaneous IR ops ------------------------------------------------ */
453 /* Evaluate numeric comparison. */
454 int lj_ir_numcmp(lua_Number a
, lua_Number b
, IROp op
)
457 case IR_EQ
: return (a
== b
);
458 case IR_NE
: return (a
!= b
);
459 case IR_LT
: return (a
< b
);
460 case IR_GE
: return (a
>= b
);
461 case IR_LE
: return (a
<= b
);
462 case IR_GT
: return (a
> b
);
463 case IR_ULT
: return !(a
>= b
);
464 case IR_UGE
: return !(a
< b
);
465 case IR_ULE
: return !(a
> b
);
466 case IR_UGT
: return !(a
<= b
);
467 default: lua_assert(0); return 0;
471 /* Evaluate string comparison. */
472 int lj_ir_strcmp(GCstr
*a
, GCstr
*b
, IROp op
)
474 int res
= lj_str_cmp(a
, b
);
476 case IR_LT
: return (res
< 0);
477 case IR_GE
: return (res
>= 0);
478 case IR_LE
: return (res
<= 0);
479 case IR_GT
: return (res
> 0);
480 default: lua_assert(0); return 0;
484 /* Rollback IR to previous state. */
485 void lj_ir_rollback(jit_State
*J
, IRRef ref
)
487 IRRef nins
= J
->cur
.nins
;
492 J
->chain
[ir
->o
] = ir
->prev
;