Mercurial

comparison third_party/luajit/src/lj_opt_mem.c @ 178:94705b5986b3

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