aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/luajit-2.0/src/lj_opt_mem.c
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/luajit-2.0/src/lj_opt_mem.c')
-rw-r--r--libraries/luajit-2.0/src/lj_opt_mem.c861
1 files changed, 861 insertions, 0 deletions
diff --git a/libraries/luajit-2.0/src/lj_opt_mem.c b/libraries/luajit-2.0/src/lj_opt_mem.c
new file mode 100644
index 0000000..a90d097
--- /dev/null
+++ b/libraries/luajit-2.0/src/lj_opt_mem.c
@@ -0,0 +1,861 @@
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-2011 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#define fright (&J->fold.right)
25
26/*
27** Caveat #1: return value is not always a TRef -- only use with tref_ref().
28** Caveat #2: FWD relies on active CSE for xREF operands -- see lj_opt_fold().
29*/
30
31/* Return values from alias analysis. */
32typedef enum {
33 ALIAS_NO, /* The two refs CANNOT alias (exact). */
34 ALIAS_MAY, /* The two refs MAY alias (inexact). */
35 ALIAS_MUST /* The two refs MUST alias (exact). */
36} AliasRet;
37
38/* -- ALOAD/HLOAD forwarding and ASTORE/HSTORE elimination ---------------- */
39
40/* Simplified escape analysis: check for intervening stores. */
41static AliasRet aa_escape(jit_State *J, IRIns *ir, IRIns *stop)
42{
43 IRRef ref = (IRRef)(ir - J->cur.ir); /* The ref that might be stored. */
44 for (ir++; ir < stop; ir++)
45 if (ir->op2 == ref &&
46 (ir->o == IR_ASTORE || ir->o == IR_HSTORE ||
47 ir->o == IR_USTORE || ir->o == IR_FSTORE))
48 return ALIAS_MAY; /* Reference was stored and might alias. */
49 return ALIAS_NO; /* Reference was not stored. */
50}
51
52/* Alias analysis for two different table references. */
53static AliasRet aa_table(jit_State *J, IRRef ta, IRRef tb)
54{
55 IRIns *taba = IR(ta), *tabb = IR(tb);
56 int newa, newb;
57 lua_assert(ta != tb);
58 lua_assert(irt_istab(taba->t) && irt_istab(tabb->t));
59 /* Disambiguate new allocations. */
60 newa = (taba->o == IR_TNEW || taba->o == IR_TDUP);
61 newb = (tabb->o == IR_TNEW || tabb->o == IR_TDUP);
62 if (newa && newb)
63 return ALIAS_NO; /* Two different allocations never alias. */
64 if (newb) { /* At least one allocation? */
65 IRIns *tmp = taba; taba = tabb; tabb = tmp;
66 } else if (!newa) {
67 return ALIAS_MAY; /* Anything else: we just don't know. */
68 }
69 return aa_escape(J, taba, tabb);
70}
71
72/* Alias analysis for array and hash access using key-based disambiguation. */
73static AliasRet aa_ahref(jit_State *J, IRIns *refa, IRIns *refb)
74{
75 IRRef ka = refa->op2;
76 IRRef kb = refb->op2;
77 IRIns *keya, *keyb;
78 IRRef ta, tb;
79 if (refa == refb)
80 return ALIAS_MUST; /* Shortcut for same refs. */
81 keya = IR(ka);
82 if (keya->o == IR_KSLOT) { ka = keya->op1; keya = IR(ka); }
83 keyb = IR(kb);
84 if (keyb->o == IR_KSLOT) { kb = keyb->op1; keyb = IR(kb); }
85 ta = (refa->o==IR_HREFK || refa->o==IR_AREF) ? IR(refa->op1)->op1 : refa->op1;
86 tb = (refb->o==IR_HREFK || refb->o==IR_AREF) ? IR(refb->op1)->op1 : refb->op1;
87 if (ka == kb) {
88 /* Same key. Check for same table with different ref (NEWREF vs. HREF). */
89 if (ta == tb)
90 return ALIAS_MUST; /* Same key, same table. */
91 else
92 return aa_table(J, ta, tb); /* Same key, possibly different table. */
93 }
94 if (irref_isk(ka) && irref_isk(kb))
95 return ALIAS_NO; /* Different constant keys. */
96 if (refa->o == IR_AREF) {
97 /* Disambiguate array references based on index arithmetic. */
98 int32_t ofsa = 0, ofsb = 0;
99 IRRef basea = ka, baseb = kb;
100 lua_assert(refb->o == IR_AREF);
101 /* Gather base and offset from t[base] or t[base+-ofs]. */
102 if (keya->o == IR_ADD && irref_isk(keya->op2)) {
103 basea = keya->op1;
104 ofsa = IR(keya->op2)->i;
105 if (basea == kb && ofsa != 0)
106 return ALIAS_NO; /* t[base+-ofs] vs. t[base]. */
107 }
108 if (keyb->o == IR_ADD && irref_isk(keyb->op2)) {
109 baseb = keyb->op1;
110 ofsb = IR(keyb->op2)->i;
111 if (ka == baseb && ofsb != 0)
112 return ALIAS_NO; /* t[base] vs. t[base+-ofs]. */
113 }
114 if (basea == baseb && ofsa != ofsb)
115 return ALIAS_NO; /* t[base+-o1] vs. t[base+-o2] and o1 != o2. */
116 } else {
117 /* Disambiguate hash references based on the type of their keys. */
118 lua_assert((refa->o==IR_HREF || refa->o==IR_HREFK || refa->o==IR_NEWREF) &&
119 (refb->o==IR_HREF || refb->o==IR_HREFK || refb->o==IR_NEWREF));
120 if (!irt_sametype(keya->t, keyb->t))
121 return ALIAS_NO; /* Different key types. */
122 }
123 if (ta == tb)
124 return ALIAS_MAY; /* Same table, cannot disambiguate keys. */
125 else
126 return aa_table(J, ta, tb); /* Try to disambiguate tables. */
127}
128
129/* Array and hash load forwarding. */
130static TRef fwd_ahload(jit_State *J, IRRef xref)
131{
132 IRIns *xr = IR(xref);
133 IRRef lim = xref; /* Search limit. */
134 IRRef ref;
135
136 /* Search for conflicting stores. */
137 ref = J->chain[fins->o+IRDELTA_L2S];
138 while (ref > xref) {
139 IRIns *store = IR(ref);
140 switch (aa_ahref(J, xr, IR(store->op1))) {
141 case ALIAS_NO: break; /* Continue searching. */
142 case ALIAS_MAY: lim = ref; goto cselim; /* Limit search for load. */
143 case ALIAS_MUST: return store->op2; /* Store forwarding. */
144 }
145 ref = store->prev;
146 }
147
148 /* No conflicting store (yet): const-fold loads from allocations. */
149 {
150 IRIns *ir = (xr->o == IR_HREFK || xr->o == IR_AREF) ? IR(xr->op1) : xr;
151 IRRef tab = ir->op1;
152 ir = IR(tab);
153 if (ir->o == IR_TNEW || (ir->o == IR_TDUP && irref_isk(xr->op2))) {
154 /* A NEWREF with a number key may end up pointing to the array part.
155 ** But it's referenced from HSTORE and not found in the ASTORE chain.
156 ** For now simply consider this a conflict without forwarding anything.
157 */
158 if (xr->o == IR_AREF) {
159 IRRef ref2 = J->chain[IR_NEWREF];
160 while (ref2 > tab) {
161 IRIns *newref = IR(ref2);
162 if (irt_isnum(IR(newref->op2)->t))
163 goto cselim;
164 ref2 = newref->prev;
165 }
166 }
167 /* NEWREF inhibits CSE for HREF, and dependent FLOADs from HREFK/AREF.
168 ** But the above search for conflicting stores was limited by xref.
169 ** So continue searching, limited by the TNEW/TDUP. Store forwarding
170 ** is ok, too. A conflict does NOT limit the search for a matching load.
171 */
172 while (ref > tab) {
173 IRIns *store = IR(ref);
174 switch (aa_ahref(J, xr, IR(store->op1))) {
175 case ALIAS_NO: break; /* Continue searching. */
176 case ALIAS_MAY: goto cselim; /* Conflicting store. */
177 case ALIAS_MUST: return store->op2; /* Store forwarding. */
178 }
179 ref = store->prev;
180 }
181 lua_assert(ir->o != IR_TNEW || irt_isnil(fins->t));
182 if (irt_ispri(fins->t)) {
183 return TREF_PRI(irt_type(fins->t));
184 } else if (irt_isnum(fins->t) || irt_isstr(fins->t)) {
185 TValue keyv;
186 cTValue *tv;
187 IRIns *key = IR(xr->op2);
188 if (key->o == IR_KSLOT) key = IR(key->op1);
189 lj_ir_kvalue(J->L, &keyv, key);
190 tv = lj_tab_get(J->L, ir_ktab(IR(ir->op1)), &keyv);
191 lua_assert(itype2irt(tv) == irt_type(fins->t));
192 if (irt_isnum(fins->t))
193 return lj_ir_knum_u64(J, tv->u64);
194 else
195 return lj_ir_kstr(J, strV(tv));
196 }
197 /* Othwerwise: don't intern as a constant. */
198 }
199 }
200
201cselim:
202 /* Try to find a matching load. Below the conflicting store, if any. */
203 ref = J->chain[fins->o];
204 while (ref > lim) {
205 IRIns *load = IR(ref);
206 if (load->op1 == xref)
207 return ref; /* Load forwarding. */
208 ref = load->prev;
209 }
210 return 0; /* Conflict or no match. */
211}
212
213/* Reassociate ALOAD across PHIs to handle t[i-1] forwarding case. */
214static TRef fwd_aload_reassoc(jit_State *J)
215{
216 IRIns *irx = IR(fins->op1);
217 IRIns *key = IR(irx->op2);
218 if (key->o == IR_ADD && irref_isk(key->op2)) {
219 IRIns *add2 = IR(key->op1);
220 if (add2->o == IR_ADD && irref_isk(add2->op2) &&
221 IR(key->op2)->i == -IR(add2->op2)->i) {
222 IRRef ref = J->chain[IR_AREF];
223 IRRef lim = add2->op1;
224 if (irx->op1 > lim) lim = irx->op1;
225 while (ref > lim) {
226 IRIns *ir = IR(ref);
227 if (ir->op1 == irx->op1 && ir->op2 == add2->op1)
228 return fwd_ahload(J, ref);
229 ref = ir->prev;
230 }
231 }
232 }
233 return 0;
234}
235
236/* ALOAD forwarding. */
237TRef LJ_FASTCALL lj_opt_fwd_aload(jit_State *J)
238{
239 IRRef ref;
240 if ((ref = fwd_ahload(J, fins->op1)) ||
241 (ref = fwd_aload_reassoc(J)))
242 return ref;
243 return EMITFOLD;
244}
245
246/* HLOAD forwarding. */
247TRef LJ_FASTCALL lj_opt_fwd_hload(jit_State *J)
248{
249 IRRef ref = fwd_ahload(J, fins->op1);
250 if (ref)
251 return ref;
252 return EMITFOLD;
253}
254
255/* Check whether HREF of TNEW/TDUP can be folded to niltv. */
256int LJ_FASTCALL lj_opt_fwd_href_nokey(jit_State *J)
257{
258 IRRef lim = fins->op1; /* Search limit. */
259 IRRef ref;
260
261 /* The key for an ASTORE may end up in the hash part after a NEWREF. */
262 if (irt_isnum(fright->t) && J->chain[IR_NEWREF] > lim) {
263 ref = J->chain[IR_ASTORE];
264 while (ref > lim) {
265 if (ref < J->chain[IR_NEWREF])
266 return 0; /* Conflict. */
267 ref = IR(ref)->prev;
268 }
269 }
270
271 /* Search for conflicting stores. */
272 ref = J->chain[IR_HSTORE];
273 while (ref > lim) {
274 IRIns *store = IR(ref);
275 if (aa_ahref(J, fins, IR(store->op1)) != ALIAS_NO)
276 return 0; /* Conflict. */
277 ref = store->prev;
278 }
279
280 return 1; /* No conflict. Can fold to niltv. */
281}
282
283/* Check whether there's no aliasing NEWREF for the left operand. */
284int LJ_FASTCALL lj_opt_fwd_tptr(jit_State *J, IRRef lim)
285{
286 IRRef ta = fins->op1;
287 IRRef ref = J->chain[IR_NEWREF];
288 while (ref > lim) {
289 IRIns *newref = IR(ref);
290 if (ta == newref->op1 || aa_table(J, ta, newref->op1) != ALIAS_NO)
291 return 0; /* Conflict. */
292 ref = newref->prev;
293 }
294 return 1; /* No conflict. Can safely FOLD/CSE. */
295}
296
297/* ASTORE/HSTORE elimination. */
298TRef LJ_FASTCALL lj_opt_dse_ahstore(jit_State *J)
299{
300 IRRef xref = fins->op1; /* xREF reference. */
301 IRRef val = fins->op2; /* Stored value reference. */
302 IRIns *xr = IR(xref);
303 IRRef1 *refp = &J->chain[fins->o];
304 IRRef ref = *refp;
305 while (ref > xref) { /* Search for redundant or conflicting stores. */
306 IRIns *store = IR(ref);
307 switch (aa_ahref(J, xr, IR(store->op1))) {
308 case ALIAS_NO:
309 break; /* Continue searching. */
310 case ALIAS_MAY: /* Store to MAYBE the same location. */
311 if (store->op2 != val) /* Conflict if the value is different. */
312 goto doemit;
313 break; /* Otherwise continue searching. */
314 case ALIAS_MUST: /* Store to the same location. */
315 if (store->op2 == val) /* Same value: drop the new store. */
316 return DROPFOLD;
317 /* Different value: try to eliminate the redundant store. */
318 if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */
319 IRIns *ir;
320 /* Check for any intervening guards (includes conflicting loads). */
321 for (ir = IR(J->cur.nins-1); ir > store; ir--)
322 if (irt_isguard(ir->t))
323 goto doemit; /* No elimination possible. */
324 /* Remove redundant store from chain and replace with NOP. */
325 *refp = store->prev;
326 store->o = IR_NOP;
327 store->t.irt = IRT_NIL;
328 store->op1 = store->op2 = 0;
329 store->prev = 0;
330 /* Now emit the new store instead. */
331 }
332 goto doemit;
333 }
334 ref = *(refp = &store->prev);
335 }
336doemit:
337 return EMITFOLD; /* Otherwise we have a conflict or simply no match. */
338}
339
340/* -- ULOAD forwarding ---------------------------------------------------- */
341
342/* The current alias analysis for upvalues is very simplistic. It only
343** disambiguates between the unique upvalues of the same function.
344** This is good enough for now, since most upvalues are read-only.
345**
346** A more precise analysis would be feasible with the help of the parser:
347** generate a unique key for every upvalue, even across all prototypes.
348** Lacking a realistic use-case, it's unclear whether this is beneficial.
349*/
350static AliasRet aa_uref(IRIns *refa, IRIns *refb)
351{
352 if (refa->o != refb->o)
353 return ALIAS_NO; /* Different UREFx type. */
354 if (refa->op1 == refb->op1) { /* Same function. */
355 if (refa->op2 == refb->op2)
356 return ALIAS_MUST; /* Same function, same upvalue idx. */
357 else
358 return ALIAS_NO; /* Same function, different upvalue idx. */
359 } else { /* Different functions, check disambiguation hash values. */
360 if (((refa->op2 ^ refb->op2) & 0xff))
361 return ALIAS_NO; /* Upvalues with different hash values cannot alias. */
362 else
363 return ALIAS_MAY; /* No conclusion can be drawn for same hash value. */
364 }
365}
366
367/* ULOAD forwarding. */
368TRef LJ_FASTCALL lj_opt_fwd_uload(jit_State *J)
369{
370 IRRef uref = fins->op1;
371 IRRef lim = uref; /* Search limit. */
372 IRIns *xr = IR(uref);
373 IRRef ref;
374
375 /* Search for conflicting stores. */
376 ref = J->chain[IR_USTORE];
377 while (ref > uref) {
378 IRIns *store = IR(ref);
379 switch (aa_uref(xr, IR(store->op1))) {
380 case ALIAS_NO: break; /* Continue searching. */
381 case ALIAS_MAY: lim = ref; goto cselim; /* Limit search for load. */
382 case ALIAS_MUST: return store->op2; /* Store forwarding. */
383 }
384 ref = store->prev;
385 }
386
387cselim:
388 /* Try to find a matching load. Below the conflicting store, if any. */
389 return lj_opt_cselim(J, lim);
390}
391
392/* USTORE elimination. */
393TRef LJ_FASTCALL lj_opt_dse_ustore(jit_State *J)
394{
395 IRRef xref = fins->op1; /* xREF reference. */
396 IRRef val = fins->op2; /* Stored value reference. */
397 IRIns *xr = IR(xref);
398 IRRef1 *refp = &J->chain[IR_USTORE];
399 IRRef ref = *refp;
400 while (ref > xref) { /* Search for redundant or conflicting stores. */
401 IRIns *store = IR(ref);
402 switch (aa_uref(xr, IR(store->op1))) {
403 case ALIAS_NO:
404 break; /* Continue searching. */
405 case ALIAS_MAY: /* Store to MAYBE the same location. */
406 if (store->op2 != val) /* Conflict if the value is different. */
407 goto doemit;
408 break; /* Otherwise continue searching. */
409 case ALIAS_MUST: /* Store to the same location. */
410 if (store->op2 == val) /* Same value: drop the new store. */
411 return DROPFOLD;
412 /* Different value: try to eliminate the redundant store. */
413 if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */
414 IRIns *ir;
415 /* Check for any intervening guards (includes conflicting loads). */
416 for (ir = IR(J->cur.nins-1); ir > store; ir--)
417 if (irt_isguard(ir->t))
418 goto doemit; /* No elimination possible. */
419 /* Remove redundant store from chain and replace with NOP. */
420 *refp = store->prev;
421 store->o = IR_NOP;
422 store->t.irt = IRT_NIL;
423 store->op1 = store->op2 = 0;
424 store->prev = 0;
425 /* Now emit the new store instead. */
426 }
427 goto doemit;
428 }
429 ref = *(refp = &store->prev);
430 }
431doemit:
432 return EMITFOLD; /* Otherwise we have a conflict or simply no match. */
433}
434
435/* -- FLOAD forwarding and FSTORE elimination ----------------------------- */
436
437/* Alias analysis for field access.
438** Field loads are cheap and field stores are rare.
439** Simple disambiguation based on field types is good enough.
440*/
441static AliasRet aa_fref(jit_State *J, IRIns *refa, IRIns *refb)
442{
443 if (refa->op2 != refb->op2)
444 return ALIAS_NO; /* Different fields. */
445 if (refa->op1 == refb->op1)
446 return ALIAS_MUST; /* Same field, same object. */
447 else if (refa->op2 >= IRFL_TAB_META && refa->op2 <= IRFL_TAB_NOMM)
448 return aa_table(J, refa->op1, refb->op1); /* Disambiguate tables. */
449 else
450 return ALIAS_MAY; /* Same field, possibly different object. */
451}
452
453/* Only the loads for mutable fields end up here (see FOLD). */
454TRef LJ_FASTCALL lj_opt_fwd_fload(jit_State *J)
455{
456 IRRef oref = fins->op1; /* Object reference. */
457 IRRef fid = fins->op2; /* Field ID. */
458 IRRef lim = oref; /* Search limit. */
459 IRRef ref;
460
461 /* Search for conflicting stores. */
462 ref = J->chain[IR_FSTORE];
463 while (ref > oref) {
464 IRIns *store = IR(ref);
465 switch (aa_fref(J, fins, IR(store->op1))) {
466 case ALIAS_NO: break; /* Continue searching. */
467 case ALIAS_MAY: lim = ref; goto cselim; /* Limit search for load. */
468 case ALIAS_MUST: return store->op2; /* Store forwarding. */
469 }
470 ref = store->prev;
471 }
472
473 /* No conflicting store: const-fold field loads from allocations. */
474 if (fid == IRFL_TAB_META) {
475 IRIns *ir = IR(oref);
476 if (ir->o == IR_TNEW || ir->o == IR_TDUP)
477 return lj_ir_knull(J, IRT_TAB);
478 }
479
480cselim:
481 /* Try to find a matching load. Below the conflicting store, if any. */
482 return lj_opt_cselim(J, lim);
483}
484
485/* FSTORE elimination. */
486TRef LJ_FASTCALL lj_opt_dse_fstore(jit_State *J)
487{
488 IRRef fref = fins->op1; /* FREF reference. */
489 IRRef val = fins->op2; /* Stored value reference. */
490 IRIns *xr = IR(fref);
491 IRRef1 *refp = &J->chain[IR_FSTORE];
492 IRRef ref = *refp;
493 while (ref > fref) { /* Search for redundant or conflicting stores. */
494 IRIns *store = IR(ref);
495 switch (aa_fref(J, xr, IR(store->op1))) {
496 case ALIAS_NO:
497 break; /* Continue searching. */
498 case ALIAS_MAY:
499 if (store->op2 != val) /* Conflict if the value is different. */
500 goto doemit;
501 break; /* Otherwise continue searching. */
502 case ALIAS_MUST:
503 if (store->op2 == val) /* Same value: drop the new store. */
504 return DROPFOLD;
505 /* Different value: try to eliminate the redundant store. */
506 if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */
507 IRIns *ir;
508 /* Check for any intervening guards or conflicting loads. */
509 for (ir = IR(J->cur.nins-1); ir > store; ir--)
510 if (irt_isguard(ir->t) || (ir->o == IR_FLOAD && ir->op2 == xr->op2))
511 goto doemit; /* No elimination possible. */
512 /* Remove redundant store from chain and replace with NOP. */
513 *refp = store->prev;
514 store->o = IR_NOP;
515 store->t.irt = IRT_NIL;
516 store->op1 = store->op2 = 0;
517 store->prev = 0;
518 /* Now emit the new store instead. */
519 }
520 goto doemit;
521 }
522 ref = *(refp = &store->prev);
523 }
524doemit:
525 return EMITFOLD; /* Otherwise we have a conflict or simply no match. */
526}
527
528/* -- XLOAD forwarding and XSTORE elimination ----------------------------- */
529
530/* Find cdata allocation for a reference (if any). */
531static IRIns *aa_findcnew(jit_State *J, IRIns *ir)
532{
533 while (ir->o == IR_ADD) {
534 if (!irref_isk(ir->op1)) {
535 IRIns *ir1 = aa_findcnew(J, IR(ir->op1)); /* Left-recursion. */
536 if (ir1) return ir1;
537 }
538 if (irref_isk(ir->op2)) return NULL;
539 ir = IR(ir->op2); /* Flatten right-recursion. */
540 }
541 return ir->o == IR_CNEW ? ir : NULL;
542}
543
544/* Alias analysis for two cdata allocations. */
545static AliasRet aa_cnew(jit_State *J, IRIns *refa, IRIns *refb)
546{
547 IRIns *cnewa = aa_findcnew(J, refa);
548 IRIns *cnewb = aa_findcnew(J, refb);
549 if (cnewa == cnewb)
550 return ALIAS_MAY; /* Same allocation or neither is an allocation. */
551 if (cnewa && cnewb)
552 return ALIAS_NO; /* Two different allocations never alias. */
553 if (cnewb) { cnewa = cnewb; refb = refa; }
554 return aa_escape(J, cnewa, refb);
555}
556
557/* Alias analysis for XLOAD/XSTORE. */
558static AliasRet aa_xref(jit_State *J, IRIns *refa, IRIns *xa, IRIns *xb)
559{
560 ptrdiff_t ofsa = 0, ofsb = 0;
561 IRIns *refb = IR(xb->op1);
562 IRIns *basea = refa, *baseb = refb;
563 /* This implements (very) strict aliasing rules.
564 ** Different types do NOT alias, except for differences in signedness.
565 ** NYI: this also prevents type punning through unions.
566 */
567 if (irt_sametype(xa->t, xb->t)) {
568 if (refa == refb)
569 return ALIAS_MUST; /* Shortcut for same refs with identical type. */
570 } else if (!(irt_typerange(xa->t, IRT_I8, IRT_U64) &&
571 ((xa->t.irt - IRT_I8) ^ (xb->t.irt - IRT_I8)) == 1)) {
572 return ALIAS_NO;
573 }
574 /* Offset-based disambiguation. */
575 if (refa->o == IR_ADD && irref_isk(refa->op2)) {
576 IRIns *irk = IR(refa->op2);
577 basea = IR(refa->op1);
578 ofsa = (LJ_64 && irk->o == IR_KINT64) ? (ptrdiff_t)ir_k64(irk)->u64 :
579 (ptrdiff_t)irk->i;
580 if (basea == refb && ofsa != 0)
581 return ALIAS_NO; /* base+-ofs vs. base. */
582 }
583 if (refb->o == IR_ADD && irref_isk(refb->op2)) {
584 IRIns *irk = IR(refb->op2);
585 baseb = IR(refb->op1);
586 ofsb = (LJ_64 && irk->o == IR_KINT64) ? (ptrdiff_t)ir_k64(irk)->u64 :
587 (ptrdiff_t)irk->i;
588 if (refa == baseb && ofsb != 0)
589 return ALIAS_NO; /* base vs. base+-ofs. */
590 }
591 if (basea == baseb) {
592 /* This assumes strictly-typed, non-overlapping accesses. */
593 if (ofsa != ofsb)
594 return ALIAS_NO; /* base+-o1 vs. base+-o2 and o1 != o2. */
595 return ALIAS_MUST; /* Unsigned vs. signed access to the same address. */
596 }
597 /* NYI: structural disambiguation. */
598 return aa_cnew(J, basea, baseb); /* Try to disambiguate allocations. */
599}
600
601/* Return CSEd reference or 0. Caveat: swaps lower ref to the right! */
602static IRRef reassoc_trycse(jit_State *J, IROp op, IRRef op1, IRRef op2)
603{
604 IRRef ref = J->chain[op];
605 IRRef lim = op1;
606 if (op2 > lim) { lim = op2; op2 = op1; op1 = lim; }
607 while (ref > lim) {
608 IRIns *ir = IR(ref);
609 if (ir->op1 == op1 && ir->op2 == op2)
610 return ref;
611 ref = ir->prev;
612 }
613 return 0;
614}
615
616/* Reassociate index references. */
617static IRRef reassoc_xref(jit_State *J, IRIns *ir)
618{
619 ptrdiff_t ofs = 0;
620 if (ir->o == IR_ADD && irref_isk(ir->op2)) { /* Get constant offset. */
621 IRIns *irk = IR(ir->op2);
622 ofs = (LJ_64 && irk->o == IR_KINT64) ? (ptrdiff_t)ir_k64(irk)->u64 :
623 (ptrdiff_t)irk->i;
624 ir = IR(ir->op1);
625 }
626 if (ir->o == IR_ADD) { /* Add of base + index. */
627 /* Index ref > base ref for loop-carried dependences. Only check op1. */
628 IRIns *ir2, *ir1 = IR(ir->op1);
629 int32_t shift = 0;
630 IRRef idxref;
631 /* Determine index shifts. Don't bother with IR_MUL here. */
632 if (ir1->o == IR_BSHL && irref_isk(ir1->op2))
633 shift = IR(ir1->op2)->i;
634 else if (ir1->o == IR_ADD && ir1->op1 == ir1->op2)
635 shift = 1;
636 else
637 ir1 = ir;
638 ir2 = IR(ir1->op1);
639 /* A non-reassociated add. Must be a loop-carried dependence. */
640 if (ir2->o == IR_ADD && irt_isint(ir2->t) && irref_isk(ir2->op2))
641 ofs += (ptrdiff_t)IR(ir2->op2)->i << shift;
642 else
643 return 0;
644 idxref = ir2->op1;
645 /* Try to CSE the reassociated chain. Give up if not found. */
646 if (ir1 != ir &&
647 !(idxref = reassoc_trycse(J, ir1->o, idxref,
648 ir1->o == IR_BSHL ? ir1->op2 : idxref)))
649 return 0;
650 if (!(idxref = reassoc_trycse(J, IR_ADD, idxref, ir->op2)))
651 return 0;
652 if (ofs != 0) {
653 IRRef refk = tref_ref(lj_ir_kintp(J, ofs));
654 if (!(idxref = reassoc_trycse(J, IR_ADD, idxref, refk)))
655 return 0;
656 }
657 return idxref; /* Success, found a reassociated index reference. Phew. */
658 }
659 return 0; /* Failure. */
660}
661
662/* XLOAD forwarding. */
663TRef LJ_FASTCALL lj_opt_fwd_xload(jit_State *J)
664{
665 IRRef xref = fins->op1;
666 IRIns *xr = IR(xref);
667 IRRef lim = xref; /* Search limit. */
668 IRRef ref;
669
670 if ((fins->op2 & IRXLOAD_READONLY))
671 goto cselim;
672 if ((fins->op2 & IRXLOAD_VOLATILE))
673 goto doemit;
674
675 /* Search for conflicting stores. */
676 ref = J->chain[IR_XSTORE];
677retry:
678 if (J->chain[IR_CALLXS] > lim) lim = J->chain[IR_CALLXS];
679 if (J->chain[IR_XBAR] > lim) lim = J->chain[IR_XBAR];
680 while (ref > lim) {
681 IRIns *store = IR(ref);
682 switch (aa_xref(J, xr, fins, store)) {
683 case ALIAS_NO: break; /* Continue searching. */
684 case ALIAS_MAY: lim = ref; goto cselim; /* Limit search for load. */
685 case ALIAS_MUST:
686 /* Emit conversion if the loaded type doesn't match the forwarded type. */
687 if (!irt_sametype(fins->t, IR(store->op2)->t)) {
688 IRType st = irt_type(fins->t);
689 if (st == IRT_I8 || st == IRT_I16) { /* Trunc + sign-extend. */
690 st |= IRCONV_SEXT;
691 } else if (st == IRT_U8 || st == IRT_U16) { /* Trunc + zero-extend. */
692 } else if (st == IRT_INT && !irt_isint(IR(store->op2)->t)) {
693 st = irt_type(IR(store->op2)->t); /* Needs dummy CONV.int.*. */
694 } else { /* I64/U64 are boxed, U32 is hidden behind a CONV.num.u32. */
695 goto store_fwd;
696 }
697 fins->ot = IRTI(IR_CONV);
698 fins->op1 = store->op2;
699 fins->op2 = (IRT_INT<<5)|st;
700 return RETRYFOLD;
701 }
702 store_fwd:
703 return store->op2; /* Store forwarding. */
704 }
705 ref = store->prev;
706 }
707
708cselim:
709 /* Try to find a matching load. Below the conflicting store, if any. */
710 ref = J->chain[IR_XLOAD];
711 while (ref > lim) {
712 /* CSE for XLOAD depends on the type, but not on the IRXLOAD_* flags. */
713 if (IR(ref)->op1 == xref && irt_sametype(IR(ref)->t, fins->t))
714 return ref;
715 ref = IR(ref)->prev;
716 }
717
718 /* Reassociate XLOAD across PHIs to handle a[i-1] forwarding case. */
719 if (!(fins->op2 & IRXLOAD_READONLY) && J->chain[IR_LOOP] &&
720 xref == fins->op1 && (xref = reassoc_xref(J, xr)) != 0) {
721 ref = J->chain[IR_XSTORE];
722 while (ref > lim) /* Skip stores that have already been checked. */
723 ref = IR(ref)->prev;
724 lim = xref;
725 xr = IR(xref);
726 goto retry; /* Retry with the reassociated reference. */
727 }
728doemit:
729 return EMITFOLD;
730}
731
732/* XSTORE elimination. */
733TRef LJ_FASTCALL lj_opt_dse_xstore(jit_State *J)
734{
735 IRRef xref = fins->op1;
736 IRIns *xr = IR(xref);
737 IRRef lim = xref; /* Search limit. */
738 IRRef val = fins->op2; /* Stored value reference. */
739 IRRef1 *refp = &J->chain[IR_XSTORE];
740 IRRef ref = *refp;
741 if (J->chain[IR_CALLXS] > lim) lim = J->chain[IR_CALLXS];
742 if (J->chain[IR_XBAR] > lim) lim = J->chain[IR_XBAR];
743 while (ref > lim) { /* Search for redundant or conflicting stores. */
744 IRIns *store = IR(ref);
745 switch (aa_xref(J, xr, fins, store)) {
746 case ALIAS_NO:
747 break; /* Continue searching. */
748 case ALIAS_MAY:
749 if (store->op2 != val) /* Conflict if the value is different. */
750 goto doemit;
751 break; /* Otherwise continue searching. */
752 case ALIAS_MUST:
753 if (store->op2 == val) /* Same value: drop the new store. */
754 return DROPFOLD;
755 /* Different value: try to eliminate the redundant store. */
756 if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */
757 IRIns *ir;
758 /* Check for any intervening guards or any XLOADs (no AA performed). */
759 for (ir = IR(J->cur.nins-1); ir > store; ir--)
760 if (irt_isguard(ir->t) || ir->o == IR_XLOAD)
761 goto doemit; /* No elimination possible. */
762 /* Remove redundant store from chain and replace with NOP. */
763 *refp = store->prev;
764 store->o = IR_NOP;
765 store->t.irt = IRT_NIL;
766 store->op1 = store->op2 = 0;
767 store->prev = 0;
768 /* Now emit the new store instead. */
769 }
770 goto doemit;
771 }
772 ref = *(refp = &store->prev);
773 }
774doemit:
775 return EMITFOLD; /* Otherwise we have a conflict or simply no match. */
776}
777
778/* -- Forwarding of lj_tab_len -------------------------------------------- */
779
780/* This is rather simplistic right now, but better than nothing. */
781TRef LJ_FASTCALL lj_opt_fwd_tab_len(jit_State *J)
782{
783 IRRef tab = fins->op1; /* Table reference. */
784 IRRef lim = tab; /* Search limit. */
785 IRRef ref;
786
787 /* Any ASTORE is a conflict and limits the search. */
788 if (J->chain[IR_ASTORE] > lim) lim = J->chain[IR_ASTORE];
789
790 /* Search for conflicting HSTORE with numeric key. */
791 ref = J->chain[IR_HSTORE];
792 while (ref > lim) {
793 IRIns *store = IR(ref);
794 IRIns *href = IR(store->op1);
795 IRIns *key = IR(href->op2);
796 if (irt_isnum(key->o == IR_KSLOT ? IR(key->op1)->t : key->t)) {
797 lim = ref; /* Conflicting store found, limits search for TLEN. */
798 break;
799 }
800 ref = store->prev;
801 }
802
803 /* Try to find a matching load. Below the conflicting store, if any. */
804 return lj_opt_cselim(J, lim);
805}
806
807/* -- ASTORE/HSTORE previous type analysis -------------------------------- */
808
809/* Check whether the previous value for a table store is non-nil.
810** This can be derived either from a previous store or from a previous
811** load (because all loads from tables perform a type check).
812**
813** The result of the analysis can be used to avoid the metatable check
814** and the guard against HREF returning niltv. Both of these are cheap,
815** so let's not spend too much effort on the analysis.
816**
817** A result of 1 is exact: previous value CANNOT be nil.
818** A result of 0 is inexact: previous value MAY be nil.
819*/
820int lj_opt_fwd_wasnonnil(jit_State *J, IROpT loadop, IRRef xref)
821{
822 /* First check stores. */
823 IRRef ref = J->chain[loadop+IRDELTA_L2S];
824 while (ref > xref) {
825 IRIns *store = IR(ref);
826 if (store->op1 == xref) { /* Same xREF. */
827 /* A nil store MAY alias, but a non-nil store MUST alias. */
828 return !irt_isnil(store->t);
829 } else if (irt_isnil(store->t)) { /* Must check any nil store. */
830 IRRef skref = IR(store->op1)->op2;
831 IRRef xkref = IR(xref)->op2;
832 /* Same key type MAY alias. Need ALOAD check due to multiple int types. */
833 if (loadop == IR_ALOAD || irt_sametype(IR(skref)->t, IR(xkref)->t)) {
834 if (skref == xkref || !irref_isk(skref) || !irref_isk(xkref))
835 return 0; /* A nil store with same const key or var key MAY alias. */
836 /* Different const keys CANNOT alias. */
837 } /* Different key types CANNOT alias. */
838 } /* Other non-nil stores MAY alias. */
839 ref = store->prev;
840 }
841
842 /* Check loads since nothing could be derived from stores. */
843 ref = J->chain[loadop];
844 while (ref > xref) {
845 IRIns *load = IR(ref);
846 if (load->op1 == xref) { /* Same xREF. */
847 /* A nil load MAY alias, but a non-nil load MUST alias. */
848 return !irt_isnil(load->t);
849 } /* Other non-nil loads MAY alias. */
850 ref = load->prev;
851 }
852 return 0; /* Nothing derived at all, previous value MAY be nil. */
853}
854
855/* ------------------------------------------------------------------------ */
856
857#undef IR
858#undef fins
859#undef fright
860
861#endif
generated by cgit v1.1 at 2024-07-01 04:18:32 +0000