luna - luajit/src/lj_opt

  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-2026 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/* Check whether there's no aliasing table.clear. */
 76static 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. */
 90int 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. */
104static 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. */
162static 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      /* Simplified here: let loop_unroll() figure out any type instability. */
221      if (ir->o == IR_TNEW) {
222	return TREF_NIL;
223      } else {
224	TValue keyv;
225	cTValue *tv;
226	IRIns *key = IR(xr->op2);
227	if (key->o == IR_KSLOT) key = IR(key->op1);
228	lj_ir_kvalue(J->L, &keyv, key);
229	tv = lj_tab_get(J->L, ir_ktab(IR(ir->op1)), &keyv);
230	if (tvispri(tv))
231	  return TREF_PRI(itype2irt(tv));
232	else if (tvisnum(tv))
233	  return lj_ir_knum_u64(J, tv->u64);
234	else if (tvisint(tv))
235	  return lj_ir_kint(J, intV(tv));
236	else if (tvistab(tv)) /* Template table nil value marker. */
237	  return TREF_NIL;
238	else if (tvisstr(tv))
239	  return lj_ir_kstr(J, strV(tv));
240      }
241      /* Othwerwise: don't intern as a constant. */
242    }
243  }
244
245cselim:
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. */
258static 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. */
281TRef 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. */
291TRef 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. */
300TRef 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. */
319docse:
320  return CSEFOLD;
321}
322
323/* Check whether HREF of TNEW/TDUP can be folded to niltv. */
324int 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. */
352TRef 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  }
390doemit:
391  return EMITFOLD;  /* Otherwise we have a conflict or simply no match. */
392}
393
394/* ALEN forwarding. */
395TRef 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  }
451doemit:
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*/
465static AliasRet aa_uref(IRIns *refa, IRIns *refb)
466{
467  if (refa->op1 == refb->op1) {  /* Same function. */
468    if (refa->op2 == refb->op2)
469      return ALIAS_MUST;  /* Same function, same upvalue idx. */
470    else
471      return ALIAS_NO;  /* Same function, different upvalue idx. */
472  } else {  /* Different functions, check disambiguation hash values. */
473    if (((refa->op2 ^ refb->op2) & 0xff)) {
474      return ALIAS_NO;  /* Upvalues with different hash values cannot alias. */
475    } else if (refa->o != refb->o) {
476      /* Different UREFx type, but need to confirm the UREFO really is open. */
477      if (irt_type(refa->t) == IRT_IGC) refa->t.irt += IRT_PGC-IRT_IGC;
478      else if (irt_type(refb->t) == IRT_IGC) refb->t.irt += IRT_PGC-IRT_IGC;
479      return ALIAS_NO;
480    } else {
481      /* No conclusion can be drawn for same hash value and same UREFx type. */
482      return ALIAS_MAY;
483    }
484  }
485}
486
487/* ULOAD forwarding. */
488TRef LJ_FASTCALL lj_opt_fwd_uload(jit_State *J)
489{
490  IRRef uref = fins->op1;
491  IRRef lim = REF_BASE;  /* Search limit. */
492  IRIns *xr = IR(uref);
493  IRRef ref;
494
495  /* Search for conflicting stores. */
496  ref = J->chain[IR_USTORE];
497  while (ref > lim) {
498    IRIns *store = IR(ref);
499    switch (aa_uref(xr, IR(store->op1))) {
500    case ALIAS_NO:   break;  /* Continue searching. */
501    case ALIAS_MAY:  lim = ref; goto cselim;  /* Limit search for load. */
502    case ALIAS_MUST: return store->op2;  /* Store forwarding. */
503    }
504    ref = store->prev;
505  }
506
507cselim:
508  /* Try to find a matching load. Below the conflicting store, if any. */
509  ref = J->chain[IR_ULOAD];
510  while (ref > lim) {
511    IRIns *ir = IR(ref);
512    if (ir->op1 == uref ||
513	(IR(ir->op1)->op12 == IR(uref)->op12 && IR(ir->op1)->o == IR(uref)->o))
514      return ref;  /* Match for identical or equal UREFx (non-CSEable UREFO). */
515    ref = ir->prev;
516  }
517  return lj_ir_emit(J);
518}
519
520/* USTORE elimination. */
521TRef LJ_FASTCALL lj_opt_dse_ustore(jit_State *J)
522{
523  IRRef xref = fins->op1;  /* xREF reference. */
524  IRRef val = fins->op2;  /* Stored value reference. */
525  IRIns *xr = IR(xref);
526  IRRef1 *refp = &J->chain[IR_USTORE];
527  IRRef ref = *refp;
528  while (ref > xref) {  /* Search for redundant or conflicting stores. */
529    IRIns *store = IR(ref);
530    switch (aa_uref(xr, IR(store->op1))) {
531    case ALIAS_NO:
532      break;  /* Continue searching. */
533    case ALIAS_MAY:	/* Store to MAYBE the same location. */
534      if (store->op2 != val)  /* Conflict if the value is different. */
535	goto doemit;
536      break;  /* Otherwise continue searching. */
537    case ALIAS_MUST:	/* Store to the same location. */
538      if (store->op2 == val)  /* Same value: drop the new store. */
539	return DROPFOLD;
540      /* Different value: try to eliminate the redundant store. */
541      if (ref > J->chain[IR_LOOP]) {  /* Quick check to avoid crossing LOOP. */
542	IRIns *ir;
543	/* Check for any intervening guards (includes conflicting loads). */
544	for (ir = IR(J->cur.nins-1); ir > store; ir--)
545	  if (irt_isguard(ir->t))
546	    goto doemit;  /* No elimination possible. */
547	/* Remove redundant store from chain and replace with NOP. */
548	*refp = store->prev;
549	lj_ir_nop(store);
550	if (ref+1 < J->cur.nins &&
551	    store[1].o == IR_OBAR && store[1].op1 == xref) {
552	  IRRef1 *bp = &J->chain[IR_OBAR];
553	  IRIns *obar;
554	  for (obar = IR(*bp); *bp > ref+1; obar = IR(*bp))
555	    bp = &obar->prev;
556	  /* Remove OBAR, too. */
557	  *bp = obar->prev;
558	  lj_ir_nop(obar);
559	}
560	/* Now emit the new store instead. */
561      }
562      goto doemit;
563    }
564    ref = *(refp = &store->prev);
565  }
566doemit:
567  return EMITFOLD;  /* Otherwise we have a conflict or simply no match. */
568}
569
570/* -- FLOAD forwarding and FSTORE elimination ----------------------------- */
571
572/* Alias analysis for field access.
573** Field loads are cheap and field stores are rare.
574** Simple disambiguation based on field types is good enough.
575*/
576static AliasRet aa_fref(jit_State *J, IRIns *refa, IRIns *refb)
577{
578  if (refa->op2 != refb->op2)
579    return ALIAS_NO;  /* Different fields. */
580  if (refa->op1 == refb->op1)
581    return ALIAS_MUST;  /* Same field, same object. */
582  else if (refa->op2 >= IRFL_TAB_META && refa->op2 <= IRFL_TAB_NOMM)
583    return aa_table(J, refa->op1, refb->op1);  /* Disambiguate tables. */
584  else
585    return ALIAS_MAY;  /* Same field, possibly different object. */
586}
587
588/* Only the loads for mutable fields end up here (see FOLD). */
589TRef LJ_FASTCALL lj_opt_fwd_fload(jit_State *J)
590{
591  IRRef oref = fins->op1;  /* Object reference. */
592  IRRef fid = fins->op2;  /* Field ID. */
593  IRRef lim = oref;  /* Search limit. */
594  IRRef ref;
595
596  /* Search for conflicting stores. */
597  ref = J->chain[IR_FSTORE];
598  while (ref > oref) {
599    IRIns *store = IR(ref);
600    switch (aa_fref(J, fins, IR(store->op1))) {
601    case ALIAS_NO:   break;  /* Continue searching. */
602    case ALIAS_MAY:  lim = ref; goto cselim;  /* Limit search for load. */
603    case ALIAS_MUST: return store->op2;  /* Store forwarding. */
604    }
605    ref = store->prev;
606  }
607
608  /* No conflicting store: const-fold field loads from allocations. */
609  if (fid == IRFL_TAB_META) {
610    IRIns *ir = IR(oref);
611    if (ir->o == IR_TNEW || ir->o == IR_TDUP)
612      return lj_ir_knull(J, IRT_TAB);
613  }
614
615cselim:
616  /* Try to find a matching load. Below the conflicting store, if any. */
617  return lj_opt_cselim(J, lim);
618}
619
620/* FSTORE elimination. */
621TRef LJ_FASTCALL lj_opt_dse_fstore(jit_State *J)
622{
623  IRRef fref = fins->op1;  /* FREF reference. */
624  IRRef val = fins->op2;  /* Stored value reference. */
625  IRIns *xr = IR(fref);
626  IRRef1 *refp = &J->chain[IR_FSTORE];
627  IRRef ref = *refp;
628  while (ref > fref) {  /* Search for redundant or conflicting stores. */
629    IRIns *store = IR(ref);
630    switch (aa_fref(J, xr, IR(store->op1))) {
631    case ALIAS_NO:
632      break;  /* Continue searching. */
633    case ALIAS_MAY:
634      if (store->op2 != val)  /* Conflict if the value is different. */
635	goto doemit;
636      break;  /* Otherwise continue searching. */
637    case ALIAS_MUST:
638      if (store->op2 == val &&
639	  !(xr->op2 >= IRFL_SBUF_W && xr->op2 <= IRFL_SBUF_R))
640	return DROPFOLD;  /* Same value: drop the new store. */
641      /* Different value: try to eliminate the redundant store. */
642      if (ref > J->chain[IR_LOOP]) {  /* Quick check to avoid crossing LOOP. */
643	IRIns *ir;
644	/* Check for any intervening guards or conflicting loads. */
645	for (ir = IR(J->cur.nins-1); ir > store; ir--)
646	  if (irt_isguard(ir->t) || (ir->o == IR_FLOAD && ir->op2 == xr->op2))
647	    goto doemit;  /* No elimination possible. */
648	/* Remove redundant store from chain and replace with NOP. */
649	*refp = store->prev;
650	lj_ir_nop(store);
651	/* Now emit the new store instead. */
652      }
653      goto doemit;
654    }
655    ref = *(refp = &store->prev);
656  }
657doemit:
658  return EMITFOLD;  /* Otherwise we have a conflict or simply no match. */
659}
660
661/* Check whether there's no aliasing buffer op between IRFL_SBUF_*. */
662int LJ_FASTCALL lj_opt_fwd_sbuf(jit_State *J, IRRef lim)
663{
664  IRRef ref;
665  if (J->chain[IR_BUFPUT] > lim)
666    return 0;  /* Conflict. */
667  ref = J->chain[IR_CALLS];
668  while (ref > lim) {
669    IRIns *ir = IR(ref);
670    if (ir->op2 >= IRCALL_lj_strfmt_putint && ir->op2 < IRCALL_lj_buf_tostr)
671      return 0;  /* Conflict. */
672    ref = ir->prev;
673  }
674  ref = J->chain[IR_CALLL];
675  while (ref > lim) {
676    IRIns *ir = IR(ref);
677    if (ir->op2 >= IRCALL_lj_strfmt_putint && ir->op2 < IRCALL_lj_buf_tostr)
678      return 0;  /* Conflict. */
679    ref = ir->prev;
680  }
681  return 1;  /* No conflict. Can safely FOLD/CSE. */
682}
683
684/* -- XLOAD forwarding and XSTORE elimination ----------------------------- */
685
686/* Find cdata allocation for a reference (if any). */
687static IRIns *aa_findcnew(jit_State *J, IRIns *ir)
688{
689  while (ir->o == IR_ADD) {
690    if (!irref_isk(ir->op1)) {
691      IRIns *ir1 = aa_findcnew(J, IR(ir->op1));  /* Left-recursion. */
692      if (ir1) return ir1;
693    }
694    if (irref_isk(ir->op2)) return NULL;
695    ir = IR(ir->op2);  /* Flatten right-recursion. */
696  }
697  return ir->o == IR_CNEW ? ir : NULL;
698}
699
700/* Alias analysis for two cdata allocations. */
701static AliasRet aa_cnew(jit_State *J, IRIns *refa, IRIns *refb)
702{
703  IRIns *cnewa = aa_findcnew(J, refa);
704  IRIns *cnewb = aa_findcnew(J, refb);
705  if (cnewa == cnewb)
706    return ALIAS_MAY;  /* Same allocation or neither is an allocation. */
707  if (cnewa && cnewb)
708    return ALIAS_NO;  /* Two different allocations never alias. */
709  if (cnewb) { cnewa = cnewb; refb = refa; }
710  return aa_escape(J, cnewa, refb);
711}
712
713/* Alias analysis for XLOAD/XSTORE. */
714static AliasRet aa_xref(jit_State *J, IRIns *refa, IRIns *xa, IRIns *xb)
715{
716  ptrdiff_t ofsa = 0, ofsb = 0;
717  IRIns *refb = IR(xb->op1);
718  IRIns *basea = refa, *baseb = refb;
719  if (refa == refb && irt_sametype(xa->t, xb->t))
720    return ALIAS_MUST;  /* Shortcut for same refs with identical type. */
721  /* Offset-based disambiguation. */
722  if (refa->o == IR_ADD && irref_isk(refa->op2)) {
723    IRIns *irk = IR(refa->op2);
724    basea = IR(refa->op1);
725    ofsa = (LJ_64 && irk->o == IR_KINT64) ? (ptrdiff_t)ir_k64(irk)->u64 :
726					    (ptrdiff_t)irk->i;
727  }
728  if (refb->o == IR_ADD && irref_isk(refb->op2)) {
729    IRIns *irk = IR(refb->op2);
730    baseb = IR(refb->op1);
731    ofsb = (LJ_64 && irk->o == IR_KINT64) ? (ptrdiff_t)ir_k64(irk)->u64 :
732					    (ptrdiff_t)irk->i;
733  }
734  /* Treat constified pointers like base vs. base+offset. */
735  if (basea->o == IR_KPTR && baseb->o == IR_KPTR) {
736    ofsb += (char *)ir_kptr(baseb) - (char *)ir_kptr(basea);
737    baseb = basea;
738  }
739  /* This implements (very) strict aliasing rules.
740  ** Different types do NOT alias, except for differences in signedness.
741  ** Type punning through unions is allowed (but forces a reload).
742  */
743  if (basea == baseb) {
744    ptrdiff_t sza = irt_size(xa->t), szb = irt_size(xb->t);
745    if (ofsa == ofsb) {
746      if (sza == szb && irt_isfp(xa->t) == irt_isfp(xb->t))
747	return ALIAS_MUST;  /* Same-sized, same-kind. May need to convert. */
748    } else if (ofsa + sza <= ofsb || ofsb + szb <= ofsa) {
749      return ALIAS_NO;  /* Non-overlapping base+-o1 vs. base+-o2. */
750    }
751    /* NYI: extract, extend or reinterpret bits (int <-> fp). */
752    return ALIAS_MAY;  /* Overlapping or type punning: force reload. */
753  }
754  if (!irt_sametype(xa->t, xb->t) &&
755      !(irt_typerange(xa->t, IRT_I8, IRT_U64) &&
756	((xa->t.irt - IRT_I8) ^ (xb->t.irt - IRT_I8)) == 1))
757    return ALIAS_NO;
758  /* NYI: structural disambiguation. */
759  return aa_cnew(J, basea, baseb);  /* Try to disambiguate allocations. */
760}
761
762/* Return CSEd reference or 0. Caveat: swaps lower ref to the right! */
763static IRRef reassoc_trycse(jit_State *J, IROp op, IRRef op1, IRRef op2)
764{
765  IRRef ref = J->chain[op];
766  IRRef lim = op1;
767  if (op2 > lim) { lim = op2; op2 = op1; op1 = lim; }
768  while (ref > lim) {
769    IRIns *ir = IR(ref);
770    if (ir->op1 == op1 && ir->op2 == op2)
771      return ref;
772    ref = ir->prev;
773  }
774  return 0;
775}
776
777/* Reassociate index references. */
778static IRRef reassoc_xref(jit_State *J, IRIns *ir)
779{
780  ptrdiff_t ofs = 0;
781  if (ir->o == IR_ADD && irref_isk(ir->op2)) {  /* Get constant offset. */
782    IRIns *irk = IR(ir->op2);
783    ofs = (LJ_64 && irk->o == IR_KINT64) ? (ptrdiff_t)ir_k64(irk)->u64 :
784					   (ptrdiff_t)irk->i;
785    ir = IR(ir->op1);
786  }
787  if (ir->o == IR_ADD) {  /* Add of base + index. */
788    /* Index ref > base ref for loop-carried dependences. Only check op1. */
789    IRIns *ir2, *ir1 = IR(ir->op1);
790    int32_t shift = 0;
791    IRRef idxref;
792    /* Determine index shifts. Don't bother with IR_MUL here. */
793    if (ir1->o == IR_BSHL && irref_isk(ir1->op2))
794      shift = IR(ir1->op2)->i;
795    else if (ir1->o == IR_ADD && ir1->op1 == ir1->op2)
796      shift = 1;
797    else
798      ir1 = ir;
799    ir2 = IR(ir1->op1);
800    /* A non-reassociated add. Must be a loop-carried dependence. */
801    if (ir2->o == IR_ADD && irt_isint(ir2->t) && irref_isk(ir2->op2))
802      ofs += (ptrdiff_t)IR(ir2->op2)->i << shift;
803    else
804      return 0;
805    idxref = ir2->op1;
806    /* Try to CSE the reassociated chain. Give up if not found. */
807    if (ir1 != ir &&
808	!(idxref = reassoc_trycse(J, ir1->o, idxref,
809				  ir1->o == IR_BSHL ? ir1->op2 : idxref)))
810      return 0;
811    if (!(idxref = reassoc_trycse(J, IR_ADD, idxref, ir->op2)))
812      return 0;
813    if (ofs != 0) {
814      IRRef refk = tref_ref(lj_ir_kintp(J, ofs));
815      if (!(idxref = reassoc_trycse(J, IR_ADD, idxref, refk)))
816	return 0;
817    }
818    return idxref;  /* Success, found a reassociated index reference. Phew. */
819  }
820  return 0;  /* Failure. */
821}
822
823/* XLOAD forwarding. */
824TRef LJ_FASTCALL lj_opt_fwd_xload(jit_State *J)
825{
826  IRRef xref = fins->op1;
827  IRIns *xr = IR(xref);
828  IRRef lim = xref;  /* Search limit. */
829  IRRef ref;
830
831  if ((fins->op2 & IRXLOAD_READONLY))
832    goto cselim;
833  if ((fins->op2 & IRXLOAD_VOLATILE))
834    goto doemit;
835
836  /* Search for conflicting stores. */
837  ref = J->chain[IR_XSTORE];
838retry:
839  if (J->chain[IR_CALLXS] > lim) lim = J->chain[IR_CALLXS];
840  if (J->chain[IR_XBAR] > lim) lim = J->chain[IR_XBAR];
841  while (ref > lim) {
842    IRIns *store = IR(ref);
843    switch (aa_xref(J, xr, fins, store)) {
844    case ALIAS_NO:   break;  /* Continue searching. */
845    case ALIAS_MAY:  lim = ref; goto cselim;  /* Limit search for load. */
846    case ALIAS_MUST:
847      /* Emit conversion if the loaded type doesn't match the forwarded type. */
848      if (!irt_sametype(fins->t, IR(store->op2)->t)) {
849	IRType dt = irt_type(fins->t), st = irt_type(IR(store->op2)->t);
850	if (dt == IRT_I8 || dt == IRT_I16) {  /* Trunc + sign-extend. */
851	  st = dt | IRCONV_SEXT;
852	  dt = IRT_INT;
853	} else if (dt == IRT_U8 || dt == IRT_U16) {  /* Trunc + zero-extend. */
854	  st = dt;
855	  dt = IRT_INT;
856	}
857	fins->ot = IRT(IR_CONV, dt);
858	fins->op1 = store->op2;
859	fins->op2 = (dt<<5)|st;
860	return RETRYFOLD;
861      }
862      return store->op2;  /* Store forwarding. */
863    }
864    ref = store->prev;
865  }
866
867cselim:
868  /* Try to find a matching load. Below the conflicting store, if any. */
869  ref = J->chain[IR_XLOAD];
870  while (ref > lim) {
871    /* CSE for XLOAD depends on the type, but not on the IRXLOAD_* flags. */
872    if (IR(ref)->op1 == xref && irt_sametype(IR(ref)->t, fins->t))
873      return ref;
874    ref = IR(ref)->prev;
875  }
876
877  /* Reassociate XLOAD across PHIs to handle a[i-1] forwarding case. */
878  if (!(fins->op2 & IRXLOAD_READONLY) && J->chain[IR_LOOP] &&
879      xref == fins->op1 && (xref = reassoc_xref(J, xr)) != 0) {
880    ref = J->chain[IR_XSTORE];
881    while (ref > lim)  /* Skip stores that have already been checked. */
882      ref = IR(ref)->prev;
883    lim = xref;
884    xr = IR(xref);
885    goto retry;  /* Retry with the reassociated reference. */
886  }
887doemit:
888  return EMITFOLD;
889}
890
891/* XSTORE elimination. */
892TRef LJ_FASTCALL lj_opt_dse_xstore(jit_State *J)
893{
894  IRRef xref = fins->op1;
895  IRIns *xr = IR(xref);
896  IRRef lim = xref;  /* Search limit. */
897  IRRef val = fins->op2;  /* Stored value reference. */
898  IRRef1 *refp = &J->chain[IR_XSTORE];
899  IRRef ref = *refp;
900  if (J->chain[IR_CALLXS] > lim) lim = J->chain[IR_CALLXS];
901  if (J->chain[IR_XBAR] > lim) lim = J->chain[IR_XBAR];
902  if (J->chain[IR_XSNEW] > lim) lim = J->chain[IR_XSNEW];
903  while (ref > lim) {  /* Search for redundant or conflicting stores. */
904    IRIns *store = IR(ref);
905    switch (aa_xref(J, xr, fins, store)) {
906    case ALIAS_NO:
907      break;  /* Continue searching. */
908    case ALIAS_MAY:
909      if (store->op2 != val)  /* Conflict if the value is different. */
910	goto doemit;
911      break;  /* Otherwise continue searching. */
912    case ALIAS_MUST:
913      if (store->op2 == val)  /* Same value: drop the new store. */
914	return DROPFOLD;
915      /* Different value: try to eliminate the redundant store. */
916      if (ref > J->chain[IR_LOOP]) {  /* Quick check to avoid crossing LOOP. */
917	IRIns *ir;
918	/* Check for any intervening guards or any XLOADs (no AA performed). */
919	for (ir = IR(J->cur.nins-1); ir > store; ir--)
920	  if (irt_isguard(ir->t) || ir->o == IR_XLOAD)
921	    goto doemit;  /* No elimination possible. */
922	/* Remove redundant store from chain and replace with NOP. */
923	*refp = store->prev;
924	lj_ir_nop(store);
925	/* Now emit the new store instead. */
926      }
927      goto doemit;
928    }
929    ref = *(refp = &store->prev);
930  }
931doemit:
932  return EMITFOLD;  /* Otherwise we have a conflict or simply no match. */
933}
934
935/* -- ASTORE/HSTORE previous type analysis -------------------------------- */
936
937/* Check whether the previous value for a table store is non-nil.
938** This can be derived either from a previous store or from a previous
939** load (because all loads from tables perform a type check).
940**
941** The result of the analysis can be used to avoid the metatable check
942** and the guard against HREF returning niltv. Both of these are cheap,
943** so let's not spend too much effort on the analysis.
944**
945** A result of 1 is exact: previous value CANNOT be nil.
946** A result of 0 is inexact: previous value MAY be nil.
947*/
948int lj_opt_fwd_wasnonnil(jit_State *J, IROpT loadop, IRRef xref)
949{
950  /* First check stores. */
951  IRRef ref = J->chain[loadop+IRDELTA_L2S];
952  while (ref > xref) {
953    IRIns *store = IR(ref);
954    if (store->op1 == xref) {  /* Same xREF. */
955      /* A nil store MAY alias, but a non-nil store MUST alias. */
956      return !irt_isnil(store->t);
957    } else if (irt_isnil(store->t)) {  /* Must check any nil store. */
958      IRRef skref = IR(store->op1)->op2;
959      IRRef xkref = IR(xref)->op2;
960      /* Same key type MAY alias. Need ALOAD check due to multiple int types. */
961      if (loadop == IR_ALOAD || irt_sametype(IR(skref)->t, IR(xkref)->t)) {
962	if (skref == xkref || !irref_isk(skref) || !irref_isk(xkref))
963	  return 0;  /* A nil store with same const key or var key MAY alias. */
964	/* Different const keys CANNOT alias. */
965      } else if (irt_isp32(IR(skref)->t) != irt_isp32(IR(xkref)->t)) {
966	return 0;  /* HREF and HREFK MAY alias. */
967      }  /* Different key types CANNOT alias. */
968    }  /* Other non-nil stores MAY alias. */
969    ref = store->prev;
970  }
971
972  /* Check loads since nothing could be derived from stores. */
973  ref = J->chain[loadop];
974  while (ref > xref) {
975    IRIns *load = IR(ref);
976    if (load->op1 == xref) {  /* Same xREF. */
977      /* A nil load MAY alias, but a non-nil load MUST alias. */
978      return !irt_isnil(load->t);
979    }  /* Other non-nil loads MAY alias. */
980    ref = load->prev;
981  }
982  return 0;  /* Nothing derived at all, previous value MAY be nil. */
983}
984
985/* ------------------------------------------------------------------------ */
986
987#undef IR
988#undef fins
989#undef fleft
990#undef fright
991
992#endif