2 ** SSA IR (Intermediate Representation) emitter.
3 ** Copyright (C) 2005-2014 Mike Pall. See Copyright Notice in luajit.h
9 /* For pointers to libc/libm functions. */
23 #include "lj_ircall.h"
29 #include "lj_carith.h"
32 #include "lj_strscan.h"
33 #include "lj_strfmt.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] = {
52 LJ_DATADEF
const uint8_t lj_ir_type_size
[IRT__MAX
+1] = {
53 #define IRTSIZE(name, size) size,
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) },
69 /* -- IR emitter ---------------------------------------------------------- */
71 /* Grow IR buffer at the top. */
72 void LJ_FASTCALL
lj_ir_growtop(jit_State
*J
)
74 IRIns
*baseir
= J
->irbuf
+ J
->irbotlim
;
75 MSize szins
= J
->irtoplim
- J
->irbotlim
;
77 baseir
= (IRIns
*)lj_mem_realloc(J
->L
, baseir
, szins
*sizeof(IRIns
),
78 2*szins
*sizeof(IRIns
));
79 J
->irtoplim
= J
->irbotlim
+ 2*szins
;
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
;
85 J
->cur
.ir
= J
->irbuf
= baseir
- J
->irbotlim
;
88 /* Grow IR buffer at the bottom or shift it up. */
89 static void lj_ir_growbot(jit_State
*J
)
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
));
101 J
->cur
.ir
= J
->irbuf
= baseir
- J
->irbotlim
;
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
));
109 J
->irtoplim
= J
->irbotlim
+ 2*szins
;
110 J
->cur
.ir
= J
->irbuf
= newbase
- J
->irbotlim
;
114 /* Emit IR without any optimizations. */
115 TRef LJ_FASTCALL
lj_ir_emit(jit_State
*J
)
117 IRRef ref
= lj_ir_nextins(J
);
120 ir
->prev
= J
->chain
[op
];
121 J
->chain
[op
] = (IRRef1
)ref
;
125 J
->guardemit
.irt
|= fins
->t
.irt
;
126 return TREF(ref
, irt_t((ir
->t
= fins
->t
)));
129 /* Emit call to a C function. */
130 TRef
lj_ir_call(jit_State
*J
, IRCallID id
, ...)
132 const CCallInfo
*ci
= &lj_ir_callinfo
[id
];
133 uint32_t n
= CCI_NARGS(ci
);
137 if ((ci
->flags
& CCI_L
)) n
--;
139 tr
= va_arg(argp
, IRRef
);
141 tr
= emitir(IRT(IR_CARG
, IRT_NIL
), tr
, va_arg(argp
, IRRef
));
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
);
148 /* -- Interning of constants ---------------------------------------------- */
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.
157 /* Get ref of next IR constant and optionally grow IR.
158 ** Note: this may invalidate all IRIns *!
160 static LJ_AINLINE IRRef
ir_nextk(jit_State
*J
)
162 IRRef ref
= J
->cur
.nk
;
163 if (LJ_UNLIKELY(ref
<= J
->irbotlim
)) lj_ir_growbot(J
);
168 /* Intern int32_t constant. */
169 TRef LJ_FASTCALL
lj_ir_kint(jit_State
*J
, int32_t k
)
171 IRIns
*ir
, *cir
= J
->cur
.ir
;
173 for (ref
= J
->chain
[IR_KINT
]; ref
; ref
= cir
[ref
].prev
)
181 ir
->prev
= J
->chain
[IR_KINT
];
182 J
->chain
[IR_KINT
] = (IRRef1
)ref
;
184 return TREF(ref
, IRT_INT
);
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.
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.
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. */
203 /* Free all chained arrays. */
204 void lj_ir_k64_freeall(jit_State
*J
)
207 for (k
= mref(J
->k64
, K64Array
); k
; ) {
208 K64Array
*next
= mref(k
->next
, K64Array
);
209 lj_mem_free(J2G(J
), k
, sizeof(K64Array
));
214 /* Find 64 bit constant in chained array or add it. */
215 cTValue
*lj_ir_k64_find(jit_State
*J
, uint64_t u64
)
217 K64Array
*k
, *kp
= NULL
;
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. */
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
);
235 setmref(kp
->next
, kn
); /* Chain to the end of the list. */
237 setmref(J
->k64
, kn
); /* Link first array. */
240 ntv
= &kp
->k
[kp
->numk
++]; /* Add to current array. */
245 /* Intern 64 bit constant, given by its address. */
246 TRef
lj_ir_k64(jit_State
*J
, IROp op
, cTValue
*tv
)
248 IRIns
*ir
, *cir
= J
->cur
.ir
;
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
)
256 lua_assert(checkptr32(tv
));
257 setmref(ir
->ptr
, tv
);
260 ir
->prev
= J
->chain
[op
];
261 J
->chain
[op
] = (IRRef1
)ref
;
266 /* Intern FP constant, given by its 64 bit pattern. */
267 TRef
lj_ir_knum_u64(jit_State
*J
, uint64_t u64
)
269 return lj_ir_k64(J
, IR_KNUM
, lj_ir_k64_find(J
, u64
));
272 /* Intern 64 bit integer constant. */
273 TRef
lj_ir_kint64(jit_State
*J
, uint64_t u64
)
275 return lj_ir_k64(J
, IR_KINT64
, lj_ir_k64_find(J
, u64
));
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
)
281 int32_t k
= lj_num2int(n
);
282 if (n
== (lua_Number
)k
) {
284 if (k
== 0) { /* Special check for -0. */
295 /* Intern number as int32_t constant if possible, otherwise as FP constant. */
296 TRef
lj_ir_knumint(jit_State
*J
, lua_Number n
)
299 if (numistrueint(n
, &k
))
300 return lj_ir_kint(J
, k
);
302 return lj_ir_knum(J
, n
);
305 /* Intern GC object "constant". */
306 TRef
lj_ir_kgc(jit_State
*J
, GCobj
*o
, IRType t
)
308 IRIns
*ir
, *cir
= J
->cur
.ir
;
310 lua_assert(!isdead(J2G(J
), o
));
311 for (ref
= J
->chain
[IR_KGC
]; ref
; ref
= cir
[ref
].prev
)
312 if (ir_kgc(&cir
[ref
]) == o
)
316 /* NOBARRIER: Current trace is a GC root. */
317 setgcref(ir
->gcr
, o
);
318 ir
->t
.irt
= (uint8_t)t
;
320 ir
->prev
= J
->chain
[IR_KGC
];
321 J
->chain
[IR_KGC
] = (IRRef1
)ref
;
326 /* Intern 32 bit pointer constant. */
327 TRef
lj_ir_kptr_(jit_State
*J
, IROp op
, void *ptr
)
329 IRIns
*ir
, *cir
= J
->cur
.ir
;
331 lua_assert((void *)(intptr_t)i32ptr(ptr
) == ptr
);
332 for (ref
= J
->chain
[op
]; ref
; ref
= cir
[ref
].prev
)
333 if (mref(cir
[ref
].ptr
, void) == ptr
)
337 setmref(ir
->ptr
, ptr
);
340 ir
->prev
= J
->chain
[op
];
341 J
->chain
[op
] = (IRRef1
)ref
;
343 return TREF(ref
, IRT_P32
);
346 /* Intern typed NULL constant. */
347 TRef
lj_ir_knull(jit_State
*J
, IRType t
)
349 IRIns
*ir
, *cir
= J
->cur
.ir
;
351 for (ref
= J
->chain
[IR_KNULL
]; ref
; ref
= cir
[ref
].prev
)
352 if (irt_t(cir
[ref
].t
) == t
)
357 ir
->t
.irt
= (uint8_t)t
;
359 ir
->prev
= J
->chain
[IR_KNULL
];
360 J
->chain
[IR_KNULL
] = (IRRef1
)ref
;
365 /* Intern key slot. */
366 TRef
lj_ir_kslot(jit_State
*J
, TRef key
, IRRef slot
)
368 IRIns
*ir
, *cir
= J
->cur
.ir
;
369 IRRef2 op12
= IRREF2((IRRef1
)key
, (IRRef1
)slot
);
371 /* Const part is not touched by CSE/DCE, so 0-65535 is ok for IRMlit here. */
372 lua_assert(tref_isk(key
) && slot
== (IRRef
)(IRRef1
)slot
);
373 for (ref
= J
->chain
[IR_KSLOT
]; ref
; ref
= cir
[ref
].prev
)
374 if (cir
[ref
].op12
== op12
)
381 ir
->prev
= J
->chain
[IR_KSLOT
];
382 J
->chain
[IR_KSLOT
] = (IRRef1
)ref
;
384 return TREF(ref
, IRT_P32
);
387 /* -- Access to IR constants ---------------------------------------------- */
389 /* Copy value of IR constant. */
390 void lj_ir_kvalue(lua_State
*L
, TValue
*tv
, const IRIns
*ir
)
393 lua_assert(ir
->o
!= IR_KSLOT
); /* Common mistake. */
395 case IR_KPRI
: setitype(tv
, irt_toitype(ir
->t
)); break;
396 case IR_KINT
: setintV(tv
, ir
->i
); break;
397 case IR_KGC
: setgcV(L
, tv
, ir_kgc(ir
), irt_toitype(ir
->t
)); break;
398 case IR_KPTR
: case IR_KKPTR
: case IR_KNULL
:
399 setlightudV(tv
, mref(ir
->ptr
, void));
401 case IR_KNUM
: setnumV(tv
, ir_knum(ir
)->n
); break;
404 GCcdata
*cd
= lj_cdata_new_(L
, CTID_INT64
, 8);
405 *(uint64_t *)cdataptr(cd
) = ir_kint64(ir
)->u64
;
406 setcdataV(L
, tv
, cd
);
410 default: lua_assert(0); break;
414 /* -- Convert IR operand types -------------------------------------------- */
416 /* Convert from string to number. */
417 TRef LJ_FASTCALL
lj_ir_tonumber(jit_State
*J
, TRef tr
)
419 if (!tref_isnumber(tr
)) {
421 tr
= emitir(IRTG(IR_STRTO
, IRT_NUM
), tr
, 0);
423 lj_trace_err(J
, LJ_TRERR_BADTYPE
);
428 /* Convert from integer or string to number. */
429 TRef LJ_FASTCALL
lj_ir_tonum(jit_State
*J
, TRef tr
)
431 if (!tref_isnum(tr
)) {
432 if (tref_isinteger(tr
))
433 tr
= emitir(IRTN(IR_CONV
), tr
, IRCONV_NUM_INT
);
434 else if (tref_isstr(tr
))
435 tr
= emitir(IRTG(IR_STRTO
, IRT_NUM
), tr
, 0);
437 lj_trace_err(J
, LJ_TRERR_BADTYPE
);
442 /* Convert from integer or number to string. */
443 TRef LJ_FASTCALL
lj_ir_tostr(jit_State
*J
, TRef tr
)
445 if (!tref_isstr(tr
)) {
446 if (!tref_isnumber(tr
))
447 lj_trace_err(J
, LJ_TRERR_BADTYPE
);
448 tr
= emitir(IRT(IR_TOSTR
, IRT_STR
), tr
,
449 tref_isnum(tr
) ? IRTOSTR_NUM
: IRTOSTR_INT
);
454 /* -- Miscellaneous IR ops ------------------------------------------------ */
456 /* Evaluate numeric comparison. */
457 int lj_ir_numcmp(lua_Number a
, lua_Number b
, IROp op
)
460 case IR_EQ
: return (a
== b
);
461 case IR_NE
: return (a
!= b
);
462 case IR_LT
: return (a
< b
);
463 case IR_GE
: return (a
>= b
);
464 case IR_LE
: return (a
<= b
);
465 case IR_GT
: return (a
> b
);
466 case IR_ULT
: return !(a
>= b
);
467 case IR_UGE
: return !(a
< b
);
468 case IR_ULE
: return !(a
> b
);
469 case IR_UGT
: return !(a
<= b
);
470 default: lua_assert(0); return 0;
474 /* Evaluate string comparison. */
475 int lj_ir_strcmp(GCstr
*a
, GCstr
*b
, IROp op
)
477 int res
= lj_str_cmp(a
, b
);
479 case IR_LT
: return (res
< 0);
480 case IR_GE
: return (res
>= 0);
481 case IR_LE
: return (res
<= 0);
482 case IR_GT
: return (res
> 0);
483 default: lua_assert(0); return 0;
487 /* Rollback IR to previous state. */
488 void lj_ir_rollback(jit_State
*J
, IRRef ref
)
490 IRRef nins
= J
->cur
.nins
;
495 J
->chain
[ir
->o
] = ir
->prev
;