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