diff options
Diffstat (limited to 'src/lj_opt_mem.c')
-rw-r--r-- | src/lj_opt_mem.c | 550 |
1 files changed, 550 insertions, 0 deletions
diff --git a/src/lj_opt_mem.c b/src/lj_opt_mem.c new file mode 100644 index 00000000..77a9c0e7 --- /dev/null +++ b/src/lj_opt_mem.c | |||
@@ -0,0 +1,550 @@ | |||
1 | /* | ||
2 | ** Memory access optimizations. | ||
3 | ** AA: Alias Analysis using high-level semantic disambiguation. | ||
4 | ** FWD: Load Forwarding (L2L) + Store Forwarding (S2L). | ||
5 | ** DSE: Dead-Store Elimination. | ||
6 | ** Copyright (C) 2005-2009 Mike Pall. See Copyright Notice in luajit.h | ||
7 | */ | ||
8 | |||
9 | #define lj_opt_mem_c | ||
10 | #define LUA_CORE | ||
11 | |||
12 | #include "lj_obj.h" | ||
13 | |||
14 | #if LJ_HASJIT | ||
15 | |||
16 | #include "lj_tab.h" | ||
17 | #include "lj_ir.h" | ||
18 | #include "lj_jit.h" | ||
19 | #include "lj_iropt.h" | ||
20 | |||
21 | /* Some local macros to save typing. Undef'd at the end. */ | ||
22 | #define IR(ref) (&J->cur.ir[(ref)]) | ||
23 | #define fins (&J->fold.ins) | ||
24 | |||
25 | /* | ||
26 | ** Caveat #1: return value is not always a TRef -- only use with tref_ref(). | ||
27 | ** Caveat #2: FWD relies on active CSE for xREF operands -- see lj_opt_fold(). | ||
28 | */ | ||
29 | |||
30 | /* Return values from alias analysis. */ | ||
31 | typedef enum { | ||
32 | ALIAS_NO, /* The two refs CANNOT alias (exact). */ | ||
33 | ALIAS_MAY, /* The two refs MAY alias (inexact). */ | ||
34 | ALIAS_MUST /* The two refs MUST alias (exact). */ | ||
35 | } AliasRet; | ||
36 | |||
37 | /* -- ALOAD/HLOAD forwarding and ASTORE/HSTORE elimination ---------------- */ | ||
38 | |||
39 | /* Alias analysis for array and hash access using key-based disambiguation. */ | ||
40 | static AliasRet aa_ahref(jit_State *J, IRIns *refa, IRIns *refb) | ||
41 | { | ||
42 | IRRef ka = refa->op2; | ||
43 | IRRef kb = refb->op2; | ||
44 | IRIns *keya, *keyb; | ||
45 | if (refa == refb) | ||
46 | return ALIAS_MUST; /* Shortcut for same refs. */ | ||
47 | keya = IR(ka); | ||
48 | if (keya->o == IR_KSLOT) { ka = keya->op1; keya = IR(ka); } | ||
49 | keyb = IR(kb); | ||
50 | if (keyb->o == IR_KSLOT) { kb = keyb->op1; keyb = IR(kb); } | ||
51 | if (ka == kb) { | ||
52 | /* Same key. Check for same table with different ref (NEWREF vs. HREF). */ | ||
53 | IRIns *ta = refa; | ||
54 | IRIns *tb = refb; | ||
55 | if (ta->o == IR_HREFK || ta->o == IR_AREF) ta = IR(ta->op1); | ||
56 | if (tb->o == IR_HREFK || tb->o == IR_AREF) tb = IR(tb->op1); | ||
57 | if (ta->op1 == tb->op1) | ||
58 | return ALIAS_MUST; /* Same key, same table. */ | ||
59 | else | ||
60 | return ALIAS_MAY; /* Same key, possibly different table. */ | ||
61 | } | ||
62 | if (irref_isk(ka) && irref_isk(kb)) | ||
63 | return ALIAS_NO; /* Different constant keys. */ | ||
64 | if (refa->o == IR_AREF) { | ||
65 | /* Disambiguate array references based on index arithmetic. */ | ||
66 | lua_assert(refb->o == IR_AREF); | ||
67 | if (refa->op1 == refb->op1) { | ||
68 | /* Same table, different non-const array keys. */ | ||
69 | int32_t ofsa = 0, ofsb = 0; | ||
70 | IRRef basea = ka, baseb = kb; | ||
71 | /* Gather base and offset from t[base] or t[base+-ofs]. */ | ||
72 | if (keya->o == IR_ADD && irref_isk(keya->op2)) { | ||
73 | basea = keya->op1; | ||
74 | ofsa = IR(keya->op2)->i; | ||
75 | if (basea == kb && ofsa != 0) | ||
76 | return ALIAS_NO; /* t[base+-ofs] vs. t[base]. */ | ||
77 | } | ||
78 | if (keyb->o == IR_ADD && irref_isk(keyb->op2)) { | ||
79 | baseb = keyb->op1; | ||
80 | ofsb = IR(keyb->op2)->i; | ||
81 | if (ka == baseb && ofsb != 0) | ||
82 | return ALIAS_NO; /* t[base] vs. t[base+-ofs]. */ | ||
83 | } | ||
84 | if (basea == baseb && ofsa != ofsb) | ||
85 | return ALIAS_NO; /* t[base+-o1] vs. t[base+-o2] and o1 != o2. */ | ||
86 | } | ||
87 | } else { | ||
88 | /* Disambiguate hash references based on the type of their keys. */ | ||
89 | lua_assert((refa->o==IR_HREF || refa->o==IR_HREFK || refa->o==IR_NEWREF) && | ||
90 | (refb->o==IR_HREF || refb->o==IR_HREFK || refb->o==IR_NEWREF)); | ||
91 | if (!irt_sametype(keya->t, keyb->t)) | ||
92 | return ALIAS_NO; /* Different key types. */ | ||
93 | } | ||
94 | return ALIAS_MAY; /* Anything else: we just don't know. */ | ||
95 | } | ||
96 | |||
97 | /* Array and hash load forwarding. */ | ||
98 | static TRef fwd_ahload(jit_State *J, IRRef xref) | ||
99 | { | ||
100 | IRIns *xr = IR(xref); | ||
101 | IRRef lim = xref; /* Search limit. */ | ||
102 | IRRef ref; | ||
103 | |||
104 | /* Search for conflicting stores. */ | ||
105 | ref = J->chain[fins->o+IRDELTA_L2S]; | ||
106 | while (ref > xref) { | ||
107 | IRIns *store = IR(ref); | ||
108 | switch (aa_ahref(J, xr, IR(store->op1))) { | ||
109 | case ALIAS_NO: break; /* Continue searching. */ | ||
110 | case ALIAS_MAY: lim = ref; goto conflict; /* Limit search for load. */ | ||
111 | case ALIAS_MUST: return store->op2; /* Store forwarding. */ | ||
112 | } | ||
113 | ref = store->prev; | ||
114 | } | ||
115 | |||
116 | /* No conflicting store (yet): const-fold loads from allocations. */ | ||
117 | { | ||
118 | IRIns *ir = (xr->o == IR_HREFK || xr->o == IR_AREF) ? IR(xr->op1) : xr; | ||
119 | IRRef tab = ir->op1; | ||
120 | ir = IR(tab); | ||
121 | if (ir->o == IR_TNEW || (ir->o == IR_TDUP && irref_isk(xr->op2))) { | ||
122 | /* A NEWREF with a number key may end up pointing to the array part. | ||
123 | ** But it's referenced from HSTORE and not found in the ASTORE chain. | ||
124 | ** For now simply consider this a conflict without forwarding anything. | ||
125 | */ | ||
126 | if (xr->o == IR_AREF) { | ||
127 | IRRef ref2 = J->chain[IR_NEWREF]; | ||
128 | while (ref2 > tab) { | ||
129 | IRIns *newref = IR(ref2); | ||
130 | if (irt_isnum(IR(newref->op2)->t)) | ||
131 | goto conflict; | ||
132 | ref2 = newref->prev; | ||
133 | } | ||
134 | } | ||
135 | /* NEWREF inhibits CSE for HREF, and dependent FLOADs from HREFK/AREF. | ||
136 | ** But the above search for conflicting stores was limited by xref. | ||
137 | ** So continue searching, limited by the TNEW/TDUP. Store forwarding | ||
138 | ** is ok, too. A conflict does NOT limit the search for a matching load. | ||
139 | */ | ||
140 | while (ref > tab) { | ||
141 | IRIns *store = IR(ref); | ||
142 | switch (aa_ahref(J, xr, IR(store->op1))) { | ||
143 | case ALIAS_NO: break; /* Continue searching. */ | ||
144 | case ALIAS_MAY: goto conflict; /* Conflicting store. */ | ||
145 | case ALIAS_MUST: return store->op2; /* Store forwarding. */ | ||
146 | } | ||
147 | ref = store->prev; | ||
148 | } | ||
149 | lua_assert(ir->o != IR_TNEW || irt_isnil(fins->t)); | ||
150 | if (irt_ispri(fins->t)) { | ||
151 | return TREF_PRI(irt_type(fins->t)); | ||
152 | } else if (irt_isnum(fins->t) || irt_isstr(fins->t)) { | ||
153 | TValue keyv; | ||
154 | cTValue *tv; | ||
155 | IRIns *key = IR(xr->op2); | ||
156 | if (key->o == IR_KSLOT) key = IR(key->op1); | ||
157 | lj_ir_kvalue(J->L, &keyv, key); | ||
158 | tv = lj_tab_get(J->L, ir_ktab(IR(ir->op1)), &keyv); | ||
159 | lua_assert(itype2irt(tv) == irt_type(fins->t)); | ||
160 | if (irt_isnum(fins->t)) | ||
161 | return lj_ir_knum_nn(J, tv->u64); | ||
162 | else | ||
163 | return lj_ir_kstr(J, strV(tv)); | ||
164 | } | ||
165 | /* Othwerwise: don't intern as a constant. */ | ||
166 | } | ||
167 | } | ||
168 | |||
169 | conflict: | ||
170 | /* Try to find a matching load. Below the conflicting store, if any. */ | ||
171 | ref = J->chain[fins->o]; | ||
172 | while (ref > lim) { | ||
173 | IRIns *load = IR(ref); | ||
174 | if (load->op1 == xref) | ||
175 | return ref; /* Load forwarding. */ | ||
176 | ref = load->prev; | ||
177 | } | ||
178 | return 0; /* Conflict or no match. */ | ||
179 | } | ||
180 | |||
181 | /* Reassociate ALOAD across PHIs to handle t[i-1] forwarding case. */ | ||
182 | static TRef fwd_aload_reassoc(jit_State *J) | ||
183 | { | ||
184 | IRIns *irx = IR(fins->op1); | ||
185 | IRIns *key = IR(irx->op2); | ||
186 | if (key->o == IR_ADD && irref_isk(key->op2)) { | ||
187 | IRIns *add2 = IR(key->op1); | ||
188 | if (add2->o == IR_ADD && irref_isk(add2->op2) && | ||
189 | IR(key->op2)->i == -IR(add2->op2)->i) { | ||
190 | IRRef ref = J->chain[IR_AREF]; | ||
191 | IRRef lim = add2->op1; | ||
192 | if (irx->op1 > lim) lim = irx->op1; | ||
193 | while (ref > lim) { | ||
194 | IRIns *ir = IR(ref); | ||
195 | if (ir->op1 == irx->op1 && ir->op2 == add2->op1) | ||
196 | return fwd_ahload(J, ref); | ||
197 | ref = ir->prev; | ||
198 | } | ||
199 | } | ||
200 | } | ||
201 | return 0; | ||
202 | } | ||
203 | |||
204 | /* ALOAD forwarding. */ | ||
205 | TRef LJ_FASTCALL lj_opt_fwd_aload(jit_State *J) | ||
206 | { | ||
207 | IRRef ref; | ||
208 | if ((ref = fwd_ahload(J, fins->op1)) || | ||
209 | (ref = fwd_aload_reassoc(J))) | ||
210 | return ref; | ||
211 | return EMITFOLD; | ||
212 | } | ||
213 | |||
214 | /* HLOAD forwarding. */ | ||
215 | TRef LJ_FASTCALL lj_opt_fwd_hload(jit_State *J) | ||
216 | { | ||
217 | IRRef ref = fwd_ahload(J, fins->op1); | ||
218 | if (ref) | ||
219 | return ref; | ||
220 | return EMITFOLD; | ||
221 | } | ||
222 | |||
223 | /* ASTORE/HSTORE elimination. */ | ||
224 | TRef LJ_FASTCALL lj_opt_dse_ahstore(jit_State *J) | ||
225 | { | ||
226 | IRRef xref = fins->op1; /* xREF reference. */ | ||
227 | IRRef val = fins->op2; /* Stored value reference. */ | ||
228 | IRIns *xr = IR(xref); | ||
229 | IRRef1 *refp = &J->chain[fins->o]; | ||
230 | IRRef ref = *refp; | ||
231 | while (ref > xref) { /* Search for redundant or conflicting stores. */ | ||
232 | IRIns *store = IR(ref); | ||
233 | switch (aa_ahref(J, xr, IR(store->op1))) { | ||
234 | case ALIAS_NO: | ||
235 | break; /* Continue searching. */ | ||
236 | case ALIAS_MAY: /* Store to MAYBE the same location. */ | ||
237 | if (store->op2 != val) /* Conflict if the value is different. */ | ||
238 | goto doemit; | ||
239 | break; /* Otherwise continue searching. */ | ||
240 | case ALIAS_MUST: /* Store to the same location. */ | ||
241 | if (store->op2 == val) /* Same value: drop the new store. */ | ||
242 | return DROPFOLD; | ||
243 | /* Different value: try to eliminate the redundant store. */ | ||
244 | if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */ | ||
245 | IRIns *ir; | ||
246 | /* Check for any intervening guards (includes conflicting loads). */ | ||
247 | for (ir = IR(J->cur.nins-1); ir > store; ir--) | ||
248 | if (irt_isguard(ir->t)) | ||
249 | goto doemit; /* No elimination possible. */ | ||
250 | /* Remove redundant store from chain and replace with NOP. */ | ||
251 | *refp = store->prev; | ||
252 | store->o = IR_NOP; /* Unchained NOP -- does anybody care? */ | ||
253 | store->t.irt = IRT_NIL; | ||
254 | store->op1 = store->op2 = 0; | ||
255 | store->prev = 0; | ||
256 | /* Now emit the new store instead. */ | ||
257 | } | ||
258 | goto doemit; | ||
259 | } | ||
260 | ref = *(refp = &store->prev); | ||
261 | } | ||
262 | doemit: | ||
263 | return EMITFOLD; /* Otherwise we have a conflict or simply no match. */ | ||
264 | } | ||
265 | |||
266 | /* -- ULOAD forwarding ---------------------------------------------------- */ | ||
267 | |||
268 | /* The current alias analysis for upvalues is very simplistic. It only | ||
269 | ** disambiguates between the unique upvalues of the same function. | ||
270 | ** This is good enough for now, since most upvalues are read-only. | ||
271 | ** | ||
272 | ** A more precise analysis would be feasible with the help of the parser: | ||
273 | ** generate a unique key for every upvalue, even across all prototypes. | ||
274 | ** Lacking a realistic use-case, it's unclear whether this is beneficial. | ||
275 | */ | ||
276 | static AliasRet aa_uref(IRIns *refa, IRIns *refb) | ||
277 | { | ||
278 | if (refa->o != refb->o) | ||
279 | return ALIAS_NO; /* Different UREFx type. */ | ||
280 | if (refa->op1 != refb->op1) | ||
281 | return ALIAS_MAY; /* Different function. */ | ||
282 | else if (refa->op2 == refb->op2) | ||
283 | return ALIAS_MUST; /* Same function, same upvalue idx. */ | ||
284 | else | ||
285 | return ALIAS_NO; /* Same function, different upvalue idx. */ | ||
286 | } | ||
287 | |||
288 | /* ULOAD forwarding. */ | ||
289 | TRef LJ_FASTCALL lj_opt_fwd_uload(jit_State *J) | ||
290 | { | ||
291 | IRRef uref = fins->op1; | ||
292 | IRRef lim = uref; /* Search limit. */ | ||
293 | IRIns *xr = IR(uref); | ||
294 | IRRef ref; | ||
295 | |||
296 | /* Search for conflicting stores. */ | ||
297 | ref = J->chain[IR_USTORE]; | ||
298 | while (ref > uref) { | ||
299 | IRIns *store = IR(ref); | ||
300 | switch (aa_uref(xr, IR(store->op1))) { | ||
301 | case ALIAS_NO: break; /* Continue searching. */ | ||
302 | case ALIAS_MAY: lim = ref; goto conflict; /* Limit search for load. */ | ||
303 | case ALIAS_MUST: return store->op2; /* Store forwarding. */ | ||
304 | } | ||
305 | ref = store->prev; | ||
306 | } | ||
307 | |||
308 | conflict: | ||
309 | /* Try to find a matching load. Below the conflicting store, if any. */ | ||
310 | ref = J->chain[IR_ULOAD]; | ||
311 | while (ref > lim) { | ||
312 | IRIns *load = IR(ref); | ||
313 | if (load->op1 == uref) | ||
314 | return ref; /* Load forwarding. */ | ||
315 | ref = load->prev; | ||
316 | } | ||
317 | return EMITFOLD; /* Conflict or no match. */ | ||
318 | } | ||
319 | |||
320 | /* USTORE elimination. */ | ||
321 | TRef LJ_FASTCALL lj_opt_dse_ustore(jit_State *J) | ||
322 | { | ||
323 | IRRef xref = fins->op1; /* xREF reference. */ | ||
324 | IRRef val = fins->op2; /* Stored value reference. */ | ||
325 | IRIns *xr = IR(xref); | ||
326 | IRRef1 *refp = &J->chain[IR_USTORE]; | ||
327 | IRRef ref = *refp; | ||
328 | while (ref > xref) { /* Search for redundant or conflicting stores. */ | ||
329 | IRIns *store = IR(ref); | ||
330 | switch (aa_uref(xr, IR(store->op1))) { | ||
331 | case ALIAS_NO: | ||
332 | break; /* Continue searching. */ | ||
333 | case ALIAS_MAY: /* Store to MAYBE the same location. */ | ||
334 | if (store->op2 != val) /* Conflict if the value is different. */ | ||
335 | goto doemit; | ||
336 | break; /* Otherwise continue searching. */ | ||
337 | case ALIAS_MUST: /* Store to the same location. */ | ||
338 | if (store->op2 == val) /* Same value: drop the new store. */ | ||
339 | return DROPFOLD; | ||
340 | /* Different value: try to eliminate the redundant store. */ | ||
341 | if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */ | ||
342 | IRIns *ir; | ||
343 | /* Check for any intervening guards (includes conflicting loads). */ | ||
344 | for (ir = IR(J->cur.nins-1); ir > store; ir--) | ||
345 | if (irt_isguard(ir->t)) | ||
346 | goto doemit; /* No elimination possible. */ | ||
347 | /* Remove redundant store from chain and replace with NOP. */ | ||
348 | *refp = store->prev; | ||
349 | store->o = IR_NOP; /* Unchained NOP -- does anybody care? */ | ||
350 | store->t.irt = IRT_NIL; | ||
351 | store->op1 = store->op2 = 0; | ||
352 | store->prev = 0; | ||
353 | /* Now emit the new store instead. */ | ||
354 | } | ||
355 | goto doemit; | ||
356 | } | ||
357 | ref = *(refp = &store->prev); | ||
358 | } | ||
359 | doemit: | ||
360 | return EMITFOLD; /* Otherwise we have a conflict or simply no match. */ | ||
361 | } | ||
362 | |||
363 | /* -- FLOAD forwarding and FSTORE elimination ----------------------------- */ | ||
364 | |||
365 | /* Alias analysis for field access. | ||
366 | ** Field loads are cheap and field stores are rare. | ||
367 | ** Simple disambiguation based on field types is good enough. | ||
368 | */ | ||
369 | static AliasRet aa_fref(IRIns *refa, IRIns *refb) | ||
370 | { | ||
371 | if (refa->op2 != refb->op2) | ||
372 | return ALIAS_NO; /* Different fields. */ | ||
373 | if (refa->op1 == refb->op1) | ||
374 | return ALIAS_MUST; /* Same field, same object. */ | ||
375 | else | ||
376 | return ALIAS_MAY; /* Same field, possibly different object. */ | ||
377 | } | ||
378 | |||
379 | /* Only the loads for mutable fields end up here (see FOLD). */ | ||
380 | TRef LJ_FASTCALL lj_opt_fwd_fload(jit_State *J) | ||
381 | { | ||
382 | IRRef oref = fins->op1; /* Object reference. */ | ||
383 | IRRef fid = fins->op2; /* Field ID. */ | ||
384 | IRRef lim = oref; /* Search limit. */ | ||
385 | IRRef ref; | ||
386 | |||
387 | /* Search for conflicting stores. */ | ||
388 | ref = J->chain[IR_FSTORE]; | ||
389 | while (ref > oref) { | ||
390 | IRIns *store = IR(ref); | ||
391 | switch (aa_fref(fins, IR(store->op1))) { | ||
392 | case ALIAS_NO: break; /* Continue searching. */ | ||
393 | case ALIAS_MAY: lim = ref; goto conflict; /* Limit search for load. */ | ||
394 | case ALIAS_MUST: return store->op2; /* Store forwarding. */ | ||
395 | } | ||
396 | ref = store->prev; | ||
397 | } | ||
398 | |||
399 | /* No conflicting store: const-fold field loads from allocations. */ | ||
400 | if (fid == IRFL_TAB_META) { | ||
401 | IRIns *ir = IR(oref); | ||
402 | if (ir->o == IR_TNEW || ir->o == IR_TDUP) | ||
403 | return lj_ir_knull(J, IRT_TAB); | ||
404 | } | ||
405 | |||
406 | conflict: | ||
407 | /* Try to find a matching load. Below the conflicting store, if any. */ | ||
408 | ref = J->chain[IR_FLOAD]; | ||
409 | while (ref > lim) { | ||
410 | IRIns *load = IR(ref); | ||
411 | if (load->op1 == oref && load->op2 == fid) | ||
412 | return ref; /* Load forwarding. */ | ||
413 | ref = load->prev; | ||
414 | } | ||
415 | return EMITFOLD; /* Otherwise we have a conflict or simply no match. */ | ||
416 | } | ||
417 | |||
418 | /* FSTORE elimination. */ | ||
419 | TRef LJ_FASTCALL lj_opt_dse_fstore(jit_State *J) | ||
420 | { | ||
421 | IRRef fref = fins->op1; /* FREF reference. */ | ||
422 | IRRef val = fins->op2; /* Stored value reference. */ | ||
423 | IRIns *xr = IR(fref); | ||
424 | IRRef1 *refp = &J->chain[IR_FSTORE]; | ||
425 | IRRef ref = *refp; | ||
426 | while (ref > fref) { /* Search for redundant or conflicting stores. */ | ||
427 | IRIns *store = IR(ref); | ||
428 | switch (aa_fref(xr, IR(store->op1))) { | ||
429 | case ALIAS_NO: | ||
430 | break; /* Continue searching. */ | ||
431 | case ALIAS_MAY: | ||
432 | if (store->op2 != val) /* Conflict if the value is different. */ | ||
433 | goto doemit; | ||
434 | break; /* Otherwise continue searching. */ | ||
435 | case ALIAS_MUST: | ||
436 | if (store->op2 == val) /* Same value: drop the new store. */ | ||
437 | return DROPFOLD; | ||
438 | /* Different value: try to eliminate the redundant store. */ | ||
439 | if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */ | ||
440 | IRIns *ir; | ||
441 | /* Check for any intervening guards or conflicting loads. */ | ||
442 | for (ir = IR(J->cur.nins-1); ir > store; ir--) | ||
443 | if (irt_isguard(ir->t) || (ir->o == IR_FLOAD && ir->op2 == xr->op2)) | ||
444 | goto doemit; /* No elimination possible. */ | ||
445 | /* Remove redundant store from chain and replace with NOP. */ | ||
446 | *refp = store->prev; | ||
447 | store->o = IR_NOP; /* Unchained NOP -- does anybody care? */ | ||
448 | store->t.irt = IRT_NIL; | ||
449 | store->op1 = store->op2 = 0; | ||
450 | store->prev = 0; | ||
451 | /* Now emit the new store instead. */ | ||
452 | } | ||
453 | goto doemit; | ||
454 | } | ||
455 | ref = *(refp = &store->prev); | ||
456 | } | ||
457 | doemit: | ||
458 | return EMITFOLD; /* Otherwise we have a conflict or simply no match. */ | ||
459 | } | ||
460 | |||
461 | /* -- TLEN forwarding ----------------------------------------------------- */ | ||
462 | |||
463 | /* This is rather simplistic right now, but better than nothing. */ | ||
464 | TRef LJ_FASTCALL lj_opt_fwd_tlen(jit_State *J) | ||
465 | { | ||
466 | IRRef tab = fins->op1; /* Table reference. */ | ||
467 | IRRef lim = tab; /* Search limit. */ | ||
468 | IRRef ref; | ||
469 | |||
470 | /* Any ASTORE is a conflict and limits the search. */ | ||
471 | if (J->chain[IR_ASTORE] > lim) lim = J->chain[IR_ASTORE]; | ||
472 | |||
473 | /* Search for conflicting HSTORE with numeric key. */ | ||
474 | ref = J->chain[IR_HSTORE]; | ||
475 | while (ref > lim) { | ||
476 | IRIns *store = IR(ref); | ||
477 | IRIns *href = IR(store->op1); | ||
478 | IRIns *key = IR(href->op2); | ||
479 | if (irt_isnum(key->o == IR_KSLOT ? IR(key->op1)->t : key->t)) { | ||
480 | lim = ref; /* Conflicting store found, limits search for TLEN. */ | ||
481 | break; | ||
482 | } | ||
483 | ref = store->prev; | ||
484 | } | ||
485 | |||
486 | /* Try to find a matching load. Below the conflicting store, if any. */ | ||
487 | ref = J->chain[IR_TLEN]; | ||
488 | while (ref > lim) { | ||
489 | IRIns *tlen = IR(ref); | ||
490 | if (tlen->op1 == tab) | ||
491 | return ref; /* Load forwarding. */ | ||
492 | ref = tlen->prev; | ||
493 | } | ||
494 | return EMITFOLD; /* Otherwise we have a conflict or simply no match. */ | ||
495 | } | ||
496 | |||
497 | /* -- ASTORE/HSTORE previous type analysis -------------------------------- */ | ||
498 | |||
499 | /* Check whether the previous value for a table store is non-nil. | ||
500 | ** This can be derived either from a previous store or from a previous | ||
501 | ** load (because all loads from tables perform a type check). | ||
502 | ** | ||
503 | ** The result of the analysis can be used to avoid the metatable check | ||
504 | ** and the guard against HREF returning niltv. Both of these are cheap, | ||
505 | ** so let's not spend too much effort on the analysis. | ||
506 | ** | ||
507 | ** A result of 1 is exact: previous value CANNOT be nil. | ||
508 | ** A result of 0 is inexact: previous value MAY be nil. | ||
509 | */ | ||
510 | int lj_opt_fwd_wasnonnil(jit_State *J, IROpT loadop, IRRef xref) | ||
511 | { | ||
512 | /* First check stores. */ | ||
513 | IRRef ref = J->chain[loadop+IRDELTA_L2S]; | ||
514 | while (ref > xref) { | ||
515 | IRIns *store = IR(ref); | ||
516 | if (store->op1 == xref) { /* Same xREF. */ | ||
517 | /* A nil store MAY alias, but a non-nil store MUST alias. */ | ||
518 | return !irt_isnil(store->t); | ||
519 | } else if (irt_isnil(store->t)) { /* Must check any nil store. */ | ||
520 | IRRef skref = IR(store->op1)->op2; | ||
521 | IRRef xkref = IR(xref)->op2; | ||
522 | /* Same key type MAY alias. */ | ||
523 | if (irt_sametype(IR(skref)->t, IR(xkref)->t)) { | ||
524 | if (skref == xkref || !irref_isk(skref) || !irref_isk(xkref)) | ||
525 | return 0; /* A nil store with same const key or var key MAY alias. */ | ||
526 | /* Different const keys CANNOT alias. */ | ||
527 | } /* Different key types CANNOT alias. */ | ||
528 | } /* Other non-nil stores MAY alias. */ | ||
529 | ref = store->prev; | ||
530 | } | ||
531 | |||
532 | /* Check loads since nothing could be derived from stores. */ | ||
533 | ref = J->chain[loadop]; | ||
534 | while (ref > xref) { | ||
535 | IRIns *load = IR(ref); | ||
536 | if (load->op1 == xref) { /* Same xREF. */ | ||
537 | /* A nil load MAY alias, but a non-nil load MUST alias. */ | ||
538 | return !irt_isnil(load->t); | ||
539 | } /* Other non-nil loads MAY alias. */ | ||
540 | ref = load->prev; | ||
541 | } | ||
542 | return 0; /* Nothing derived at all, previous value MAY be nil. */ | ||
543 | } | ||
544 | |||
545 | /* ------------------------------------------------------------------------ */ | ||
546 | |||
547 | #undef IR | ||
548 | #undef fins | ||
549 | |||
550 | #endif | ||