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