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