summaryrefslogtreecommitdiff
path: root/src/lj_ir.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/lj_ir.h')
-rw-r--r--src/lj_ir.h429
1 files changed, 429 insertions, 0 deletions
diff --git a/src/lj_ir.h b/src/lj_ir.h
new file mode 100644
index 00000000..a6973a81
--- /dev/null
+++ b/src/lj_ir.h
@@ -0,0 +1,429 @@
1/*
2** SSA IR (Intermediate Representation) format.
3** Copyright (C) 2005-2009 Mike Pall. See Copyright Notice in luajit.h
4*/
5
6#ifndef _LJ_IR_H
7#define _LJ_IR_H
8
9#include "lj_obj.h"
10
11/* IR instruction definition. Order matters, see below. */
12#define IRDEF(_) \
13 /* Miscellaneous ops. */ \
14 _(NOP, N , ___, ___) \
15 _(BASE, N , lit, lit) \
16 _(LOOP, G , ___, ___) \
17 _(PHI, S , ref, ref) \
18 _(RENAME, S , ref, lit) \
19 \
20 /* Constants. */ \
21 _(KPRI, N , ___, ___) \
22 _(KINT, N , cst, ___) \
23 _(KGC, N , cst, ___) \
24 _(KPTR, N , cst, ___) \
25 _(KNULL, N , cst, ___) \
26 _(KNUM, N , cst, ___) \
27 _(KSLOT, N , ref, lit) \
28 \
29 /* Guarded assertions. */ \
30 /* Must be properly aligned to flip opposites (^1) and (un)ordered (^4). */ \
31 _(EQ, GC, ref, ref) \
32 _(NE, GC, ref, ref) \
33 \
34 _(ABC, G , ref, ref) \
35 _(FRAME, G , ref, ref) \
36 \
37 _(LT, G , ref, ref) \
38 _(GE, G , ref, ref) \
39 _(LE, G , ref, ref) \
40 _(GT, G , ref, ref) \
41 \
42 _(ULT, G , ref, ref) \
43 _(UGE, G , ref, ref) \
44 _(ULE, G , ref, ref) \
45 _(UGT, G , ref, ref) \
46 \
47 /* Bit ops. */ \
48 _(BNOT, N , ref, ___) \
49 _(BSWAP, N , ref, ___) \
50 _(BAND, C , ref, ref) \
51 _(BOR, C , ref, ref) \
52 _(BXOR, C , ref, ref) \
53 _(BSHL, N , ref, ref) \
54 _(BSHR, N , ref, ref) \
55 _(BSAR, N , ref, ref) \
56 _(BROL, N , ref, ref) \
57 _(BROR, N , ref, ref) \
58 \
59 /* Arithmetic ops. ORDER ARITH (FPMATH/POWI take the space for MOD/POW). */ \
60 _(ADD, C , ref, ref) \
61 _(SUB, N , ref, ref) \
62 _(MUL, C , ref, ref) \
63 _(DIV, N , ref, ref) \
64 \
65 _(FPMATH, N , ref, lit) \
66 _(POWI, N , ref, ref) \
67 \
68 _(NEG, N , ref, ref) \
69 _(ABS, N , ref, ref) \
70 _(ATAN2, N , ref, ref) \
71 _(LDEXP, N , ref, ref) \
72 _(MIN, C , ref, ref) \
73 _(MAX, C , ref, ref) \
74 \
75 /* Overflow-checking arithmetic ops. */ \
76 _(ADDOV, GC, ref, ref) \
77 _(SUBOV, G , ref, ref) \
78 \
79 /* Memory ops. A = array, H = hash, U = upvalue, F = field, S = stack. */ \
80 \
81 /* Memory references. */ \
82 _(AREF, R , ref, ref) \
83 _(HREFK, RG, ref, ref) \
84 _(HREF, L , ref, ref) \
85 _(NEWREF, S , ref, ref) \
86 _(UREFO, LG, ref, lit) \
87 _(UREFC, LG, ref, lit) \
88 _(FREF, R , ref, lit) \
89 _(STRREF, N , ref, ref) \
90 \
91 /* Loads and Stores. These must be in the same order. */ \
92 _(ALOAD, LG, ref, ___) \
93 _(HLOAD, LG, ref, ___) \
94 _(ULOAD, LG, ref, ___) \
95 _(FLOAD, L , ref, lit) \
96 _(SLOAD, LG, lit, lit) \
97 _(XLOAD, L , ref, lit) \
98 \
99 _(ASTORE, S , ref, ref) \
100 _(HSTORE, S , ref, ref) \
101 _(USTORE, S , ref, ref) \
102 _(FSTORE, S , ref, ref) \
103 \
104 /* String ops. */ \
105 _(SNEW, N , ref, ref) \
106 \
107 /* Table ops. */ \
108 _(TNEW, A , lit, lit) \
109 _(TDUP, A , ref, ___) \
110 _(TLEN, L , ref, ___) \
111 _(TBAR, S , ref, ___) \
112 _(OBAR, S , ref, ref) \
113 \
114 /* Type conversions. */ \
115 _(TONUM, N , ref, ___) \
116 _(TOINT, N , ref, lit) \
117 _(TOBIT, N , ref, ref) \
118 _(TOSTR, N , ref, ___) \
119 _(STRTO, G , ref, ___) \
120 \
121 /* End of list. */
122
123/* IR opcodes (max. 256). */
124typedef enum {
125#define IRENUM(name, m, m1, m2) IR_##name,
126IRDEF(IRENUM)
127#undef IRENUM
128 IR__MAX
129} IROp;
130
131/* Stored opcode. */
132typedef uint8_t IROp1;
133
134LJ_STATIC_ASSERT(((int)IR_EQ^1) == (int)IR_NE);
135LJ_STATIC_ASSERT(((int)IR_LT^1) == (int)IR_GE);
136LJ_STATIC_ASSERT(((int)IR_LE^1) == (int)IR_GT);
137LJ_STATIC_ASSERT(((int)IR_LT^3) == (int)IR_GT);
138LJ_STATIC_ASSERT(((int)IR_LT^4) == (int)IR_ULT);
139
140/* Delta between xLOAD and xSTORE. */
141#define IRDELTA_L2S ((int)IR_ASTORE - (int)IR_ALOAD)
142
143LJ_STATIC_ASSERT((int)IR_HLOAD + IRDELTA_L2S == (int)IR_HSTORE);
144LJ_STATIC_ASSERT((int)IR_ULOAD + IRDELTA_L2S == (int)IR_USTORE);
145LJ_STATIC_ASSERT((int)IR_FLOAD + IRDELTA_L2S == (int)IR_FSTORE);
146
147/* FPMATH sub-functions. ORDER FPM. */
148#define IRFPMDEF(_) \
149 _(FLOOR) _(CEIL) _(TRUNC) /* Must be first and in this order. */ \
150 _(SQRT) _(EXP) _(EXP2) _(LOG) _(LOG2) _(LOG10) \
151 _(SIN) _(COS) _(TAN) \
152 _(OTHER)
153
154typedef enum {
155#define FPMENUM(name) IRFPM_##name,
156IRFPMDEF(FPMENUM)
157#undef FPMENUM
158 IRFPM__MAX
159} IRFPMathOp;
160
161/* FLOAD field IDs. */
162#define IRFLDEF(_) \
163 _(STR_LEN, GCstr, len) \
164 _(FUNC_ENV, GCfunc, l.env) \
165 _(TAB_META, GCtab, metatable) \
166 _(TAB_ARRAY, GCtab, array) \
167 _(TAB_NODE, GCtab, node) \
168 _(TAB_ASIZE, GCtab, asize) \
169 _(TAB_HMASK, GCtab, hmask) \
170 _(TAB_NOMM, GCtab, nomm) \
171 _(UDATA_META, GCudata, metatable)
172
173typedef enum {
174#define FLENUM(name, type, field) IRFL_##name,
175IRFLDEF(FLENUM)
176#undef FLENUM
177 IRFL__MAX
178} IRFieldID;
179
180/* SLOAD mode bits, stored in op2. */
181#define IRSLOAD_INHERIT 1 /* Inherited by exits/side traces. */
182#define IRSLOAD_READONLY 2 /* Read-only, omit slot store. */
183#define IRSLOAD_PARENT 4 /* Coalesce with parent trace. */
184
185/* XLOAD mode, stored in op2. */
186#define IRXLOAD_UNALIGNED 1
187
188/* TOINT mode, stored in op2. Ordered by strength of the checks. */
189#define IRTOINT_CHECK 0 /* Number checked for integerness. */
190#define IRTOINT_INDEX 1 /* Checked + special backprop rules. */
191#define IRTOINT_ANY 2 /* Any FP number is ok. */
192#define IRTOINT_TOBIT 3 /* Cache only: TOBIT conversion. */
193
194/* IR operand mode (2 bit). */
195typedef enum {
196 IRMref, /* IR reference. */
197 IRMlit, /* 16 bit unsigned literal. */
198 IRMcst, /* Constant literal: i, gcr or ptr. */
199 IRMnone /* Unused operand. */
200} IRMode;
201#define IRM___ IRMnone
202
203/* Mode bits: Commutative, {Normal/Ref, Alloc, Load, Store}, Guard. */
204#define IRM_C 0x10
205
206#define IRM_N 0x00
207#define IRM_R IRM_N
208#define IRM_A 0x20
209#define IRM_L 0x40
210#define IRM_S 0x60
211
212#define IRM_G 0x80
213
214#define IRM_GC (IRM_G|IRM_C)
215#define IRM_RG (IRM_R|IRM_G)
216#define IRM_LG (IRM_L|IRM_G)
217
218#define irm_op1(m) (cast(IRMode, (m)&3))
219#define irm_op2(m) (cast(IRMode, ((m)>>2)&3))
220#define irm_iscomm(m) ((m) & IRM_C)
221#define irm_kind(m) ((m) & IRM_S)
222#define irm_isguard(m) ((m) & IRM_G)
223/* Stores or any other op with a guard has a side-effect. */
224#define irm_sideeff(m) ((m) >= IRM_S)
225
226#define IRMODE(name, m, m1, m2) ((IRM##m1)|((IRM##m2)<<2)|(IRM_##m)),
227
228LJ_DATA const uint8_t lj_ir_mode[IR__MAX+1];
229
230/* IR result type and flags (8 bit). */
231typedef enum {
232 /* Map of itypes to non-negative numbers. ORDER LJ_T */
233 IRT_NIL,
234 IRT_FALSE,
235 IRT_TRUE,
236 IRT_LIGHTUD,
237 /* GCobj types are from here ... */
238 IRT_STR,
239 IRT_PTR, /* IRT_PTR never escapes the IR (map of LJ_TUPVAL). */
240 IRT_THREAD,
241 IRT_PROTO,
242 IRT_FUNC,
243 IRT_9, /* LJ_TDEADKEY is never used in the IR. */
244 IRT_TAB,
245 IRT_UDATA,
246 /* ... until here. */
247 IRT_NUM,
248 /* The various integers are only used in the IR and can only escape to
249 ** a TValue after implicit or explicit conversion (TONUM). Their types
250 ** must be contiguous and next to IRT_NUM (see the typerange macros below).
251 */
252 IRT_INT,
253 IRT_I8,
254 IRT_U8,
255 IRT_I16,
256 IRT_U16,
257 /* There is room for 14 more types. */
258
259 /* Additional flags. */
260 IRT_MARK = 0x20, /* Marker for misc. purposes. */
261 IRT_GUARD = 0x40, /* Instruction is a guard. */
262 IRT_ISPHI = 0x80, /* Instruction is left or right PHI operand. */
263
264 /* Masks. */
265 IRT_TYPE = 0x1f,
266 IRT_T = 0xff
267} IRType;
268
269#define irtype_ispri(irt) ((uint32_t)(irt) <= IRT_TRUE)
270
271/* Stored IRType. */
272typedef struct IRType1 { uint8_t irt; } IRType1;
273
274#define IRT(o, t) ((uint32_t)(((o)<<8) | (t)))
275#define IRTI(o) (IRT((o), IRT_INT))
276#define IRTN(o) (IRT((o), IRT_NUM))
277#define IRTG(o, t) (IRT((o), IRT_GUARD|(t)))
278#define IRTGI(o) (IRT((o), IRT_GUARD|IRT_INT))
279
280#define irt_t(t) (cast(IRType, (t).irt))
281#define irt_type(t) (cast(IRType, (t).irt & IRT_TYPE))
282#define irt_sametype(t1, t2) ((((t1).irt ^ (t2).irt) & IRT_TYPE) == 0)
283#define irt_typerange(t, first, last) \
284 ((uint32_t)((t).irt & IRT_TYPE) - (uint32_t)(first) <= (uint32_t)(last-first))
285
286#define irt_isnil(t) (irt_type(t) == IRT_NIL)
287#define irt_ispri(t) ((uint32_t)irt_type(t) <= IRT_TRUE)
288#define irt_isstr(t) (irt_type(t) == IRT_STR)
289#define irt_isfunc(t) (irt_type(t) == IRT_FUNC)
290#define irt_istab(t) (irt_type(t) == IRT_TAB)
291#define irt_isnum(t) (irt_type(t) == IRT_NUM)
292#define irt_isint(t) (irt_type(t) == IRT_INT)
293#define irt_isi8(t) (irt_type(t) == IRT_I8)
294#define irt_isu8(t) (irt_type(t) == IRT_U8)
295#define irt_isi16(t) (irt_type(t) == IRT_I16)
296#define irt_isu16(t) (irt_type(t) == IRT_U16)
297
298#define irt_isinteger(t) (irt_typerange((t), IRT_INT, IRT_U16))
299#define irt_isgcv(t) (irt_typerange((t), IRT_STR, IRT_UDATA))
300#define irt_isaddr(t) (irt_typerange((t), IRT_LIGHTUD, IRT_UDATA))
301
302#define itype2irt(tv) \
303 (~uitype(tv) < IRT_NUM ? cast(IRType, ~uitype(tv)) : IRT_NUM)
304#define irt_toitype(t) ((int32_t)~(uint32_t)irt_type(t))
305
306#define irt_isguard(t) ((t).irt & IRT_GUARD)
307#define irt_ismarked(t) ((t).irt & IRT_MARK)
308#define irt_setmark(t) ((t).irt |= IRT_MARK)
309#define irt_clearmark(t) ((t).irt &= ~IRT_MARK)
310#define irt_isphi(t) ((t).irt & IRT_ISPHI)
311#define irt_setphi(t) ((t).irt |= IRT_ISPHI)
312#define irt_clearphi(t) ((t).irt &= ~IRT_ISPHI)
313
314/* Stored combined IR opcode and type. */
315typedef uint16_t IROpT;
316
317/* IR references. */
318typedef uint16_t IRRef1; /* One stored reference. */
319typedef uint32_t IRRef2; /* Two stored references. */
320typedef uint32_t IRRef; /* Used to pass around references. */
321
322/* Fixed references. */
323enum {
324 REF_BIAS = 0x8000,
325 REF_TRUE = REF_BIAS-3,
326 REF_FALSE = REF_BIAS-2,
327 REF_NIL = REF_BIAS-1, /* \--- Constants grow downwards. */
328 REF_BASE = REF_BIAS, /* /--- IR grows upwards. */
329 REF_FIRST = REF_BIAS+1,
330 REF_DROP = 0xffff
331};
332
333/* Note: IRMlit operands must be < REF_BIAS, too!
334** This allows for fast and uniform manipulation of all operands
335** without looking up the operand mode in lj_ir_mode:
336** - CSE calculates the maximum reference of two operands.
337** This must work with mixed reference/literal operands, too.
338** - DCE marking only checks for operand >= REF_BIAS.
339** - LOOP needs to substitute reference operands.
340** Constant references and literals must not be modified.
341*/
342
343#define IRREF2(lo, hi) ((IRRef2)(lo) | ((IRRef2)(hi) << 16))
344
345#define irref_isk(ref) ((ref) < REF_BIAS)
346
347/* Tagged IR references. */
348typedef uint32_t TRef;
349
350#define TREF(ref, t) (cast(TRef, (ref) + ((t)<<16)))
351
352#define tref_ref(tr) (cast(IRRef1, (tr)))
353#define tref_t(tr) (cast(IRType, (tr)>>16))
354#define tref_type(tr) (cast(IRType, ((tr)>>16) & IRT_TYPE))
355#define tref_typerange(tr, first, last) \
356 ((((tr)>>16) & IRT_TYPE) - (TRef)(first) <= (TRef)(last-first))
357
358#define tref_istype(tr, t) (((tr) & (IRT_TYPE<<16)) == ((t)<<16))
359#define tref_isnil(tr) (tref_istype((tr), IRT_NIL))
360#define tref_isfalse(tr) (tref_istype((tr), IRT_FALSE))
361#define tref_istrue(tr) (tref_istype((tr), IRT_TRUE))
362#define tref_isstr(tr) (tref_istype((tr), IRT_STR))
363#define tref_isfunc(tr) (tref_istype((tr), IRT_FUNC))
364#define tref_istab(tr) (tref_istype((tr), IRT_TAB))
365#define tref_isudata(tr) (tref_istype((tr), IRT_UDATA))
366#define tref_isnum(tr) (tref_istype((tr), IRT_NUM))
367#define tref_isint(tr) (tref_istype((tr), IRT_INT))
368
369#define tref_isbool(tr) (tref_typerange((tr), IRT_FALSE, IRT_TRUE))
370#define tref_ispri(tr) (tref_typerange((tr), IRT_NIL, IRT_TRUE))
371#define tref_istruecond(tr) (!tref_typerange((tr), IRT_NIL, IRT_FALSE))
372#define tref_isinteger(tr) (tref_typerange((tr), IRT_INT, IRT_U16))
373#define tref_isnumber(tr) (tref_typerange((tr), IRT_NUM, IRT_U16))
374#define tref_isnumber_str(tr) (tref_isnumber((tr)) || tref_isstr((tr)))
375#define tref_isgcv(tr) (tref_typerange((tr), IRT_STR, IRT_UDATA))
376
377#define tref_isk(tr) (irref_isk(tref_ref((tr))))
378#define tref_isk2(tr1, tr2) (irref_isk(tref_ref((tr1) | (tr2))))
379
380#define TREF_PRI(t) (TREF(REF_NIL-(t), (t)))
381#define TREF_NIL (TREF_PRI(IRT_NIL))
382#define TREF_FALSE (TREF_PRI(IRT_FALSE))
383#define TREF_TRUE (TREF_PRI(IRT_TRUE))
384
385/* IR instruction format (64 bit).
386**
387** 16 16 8 8 8 8
388** +-------+-------+---+---+---+---+
389** | op1 | op2 | t | o | r | s |
390** +-------+-------+---+---+---+---+
391** | op12/i/gco | ot | prev | (alternative fields in union)
392** +---------------+-------+-------+
393** 32 16 16
394**
395** prev is only valid prior to register allocation and then reused for r + s.
396*/
397
398typedef union IRIns {
399 struct {
400 LJ_ENDIAN_LOHI(
401 IRRef1 op1; /* IR operand 1. */
402 , IRRef1 op2; /* IR operand 2. */
403 )
404 IROpT ot; /* IR opcode and type (overlaps t and o). */
405 IRRef1 prev; /* Previous ins in same chain (overlaps r and s). */
406 };
407 struct {
408 IRRef2 op12; /* IR operand 1 and 2 (overlaps op1 and op2). */
409 LJ_ENDIAN_LOHI(
410 IRType1 t; /* IR type. */
411 , IROp1 o; /* IR opcode. */
412 )
413 LJ_ENDIAN_LOHI(
414 uint8_t r; /* Register allocation (overlaps prev). */
415 , uint8_t s; /* Spill slot allocation (overlaps prev). */
416 )
417 };
418 int32_t i; /* 32 bit signed integer literal (overlaps op12). */
419 GCRef gcr; /* GCobj constant (overlaps op12). */
420 MRef ptr; /* Pointer constant (overlaps op12). */
421} IRIns;
422
423#define ir_kgc(ir) (gcref((ir)->gcr))
424#define ir_kstr(ir) (gco2str(ir_kgc((ir))))
425#define ir_ktab(ir) (gco2tab(ir_kgc((ir))))
426#define ir_kfunc(ir) (gco2func(ir_kgc((ir))))
427#define ir_knum(ir) (mref((ir)->ptr, cTValue))
428
429#endif