root/lj_opt_mem.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. aa_escape
  2. aa_table
  3. aa_ahref
  4. fwd_ahload
  5. fwd_aload_reassoc
  6. lj_opt_fwd_aload
  7. lj_opt_fwd_hload
  8. lj_opt_fwd_hrefk
  9. lj_opt_fwd_href_nokey
  10. lj_opt_fwd_tptr
  11. lj_opt_dse_ahstore
  12. aa_uref
  13. lj_opt_fwd_uload
  14. lj_opt_dse_ustore
  15. aa_fref
  16. lj_opt_fwd_fload
  17. lj_opt_dse_fstore
  18. aa_findcnew
  19. aa_cnew
  20. aa_xref
  21. reassoc_trycse
  22. reassoc_xref
  23. lj_opt_fwd_xload
  24. lj_opt_dse_xstore
  25. lj_opt_fwd_tab_len
  26. lj_opt_fwd_wasnonnil

   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-2017 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. */
  33 typedef 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. */
  42 static 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. */
  54 static 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. */
  74 static 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. */
 131 static 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 
 205 cselim:
 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. */
 218 static 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. */
 241 TRef 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. */
 251 TRef 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. */
 260 TRef 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. */
 279 docse:
 280   return CSEFOLD;
 281 }
 282 
 283 /* Check whether HREF of TNEW/TDUP can be folded to niltv. */
 284 int 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. */
 312 int 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. */
 326 TRef 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   }
 364 doemit:
 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 */
 378 static 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. */
 396 TRef 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 
 415 cselim:
 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. */
 430 TRef 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   }
 481 doemit:
 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 */
 491 static 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). */
 504 TRef 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 
 530 cselim:
 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. */
 536 TRef 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   }
 574 doemit:
 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). */
 581 static 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. */
 595 static 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. */
 608 static 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! */
 657 static 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. */
 672 static 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. */
 718 TRef 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];
 732 retry:
 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 dt = irt_type(fins->t), st = irt_type(IR(store->op2)->t);
 744         if (dt == IRT_I8 || dt == IRT_I16) {  /* Trunc + sign-extend. */
 745           st = dt | IRCONV_SEXT;
 746           dt = IRT_INT;
 747         } else if (dt == IRT_U8 || dt == IRT_U16) {  /* Trunc + zero-extend. */
 748           st = dt;
 749           dt = IRT_INT;
 750         }
 751         fins->ot = IRT(IR_CONV, dt);
 752         fins->op1 = store->op2;
 753         fins->op2 = (dt<<5)|st;
 754         return RETRYFOLD;
 755       }
 756       return store->op2;  /* Store forwarding. */
 757     }
 758     ref = store->prev;
 759   }
 760 
 761 cselim:
 762   /* Try to find a matching load. Below the conflicting store, if any. */
 763   ref = J->chain[IR_XLOAD];
 764   while (ref > lim) {
 765     /* CSE for XLOAD depends on the type, but not on the IRXLOAD_* flags. */
 766     if (IR(ref)->op1 == xref && irt_sametype(IR(ref)->t, fins->t))
 767       return ref;
 768     ref = IR(ref)->prev;
 769   }
 770 
 771   /* Reassociate XLOAD across PHIs to handle a[i-1] forwarding case. */
 772   if (!(fins->op2 & IRXLOAD_READONLY) && J->chain[IR_LOOP] &&
 773       xref == fins->op1 && (xref = reassoc_xref(J, xr)) != 0) {
 774     ref = J->chain[IR_XSTORE];
 775     while (ref > lim)  /* Skip stores that have already been checked. */
 776       ref = IR(ref)->prev;
 777     lim = xref;
 778     xr = IR(xref);
 779     goto retry;  /* Retry with the reassociated reference. */
 780   }
 781 doemit:
 782   return EMITFOLD;
 783 }
 784 
 785 /* XSTORE elimination. */
 786 TRef LJ_FASTCALL lj_opt_dse_xstore(jit_State *J)
 787 {
 788   IRRef xref = fins->op1;
 789   IRIns *xr = IR(xref);
 790   IRRef lim = xref;  /* Search limit. */
 791   IRRef val = fins->op2;  /* Stored value reference. */
 792   IRRef1 *refp = &J->chain[IR_XSTORE];
 793   IRRef ref = *refp;
 794   if (J->chain[IR_CALLXS] > lim) lim = J->chain[IR_CALLXS];
 795   if (J->chain[IR_XBAR] > lim) lim = J->chain[IR_XBAR];
 796   if (J->chain[IR_XSNEW] > lim) lim = J->chain[IR_XSNEW];
 797   while (ref > lim) {  /* Search for redundant or conflicting stores. */
 798     IRIns *store = IR(ref);
 799     switch (aa_xref(J, xr, fins, store)) {
 800     case ALIAS_NO:
 801       break;  /* Continue searching. */
 802     case ALIAS_MAY:
 803       if (store->op2 != val)  /* Conflict if the value is different. */
 804         goto doemit;
 805       break;  /* Otherwise continue searching. */
 806     case ALIAS_MUST:
 807       if (store->op2 == val)  /* Same value: drop the new store. */
 808         return DROPFOLD;
 809       /* Different value: try to eliminate the redundant store. */
 810       if (ref > J->chain[IR_LOOP]) {  /* Quick check to avoid crossing LOOP. */
 811         IRIns *ir;
 812         /* Check for any intervening guards or any XLOADs (no AA performed). */
 813         for (ir = IR(J->cur.nins-1); ir > store; ir--)
 814           if (irt_isguard(ir->t) || ir->o == IR_XLOAD)
 815             goto doemit;  /* No elimination possible. */
 816         /* Remove redundant store from chain and replace with NOP. */
 817         *refp = store->prev;
 818         store->o = IR_NOP;
 819         store->t.irt = IRT_NIL;
 820         store->op1 = store->op2 = 0;
 821         store->prev = 0;
 822         /* Now emit the new store instead. */
 823       }
 824       goto doemit;
 825     }
 826     ref = *(refp = &store->prev);
 827   }
 828 doemit:
 829   return EMITFOLD;  /* Otherwise we have a conflict or simply no match. */
 830 }
 831 
 832 /* -- Forwarding of lj_tab_len -------------------------------------------- */
 833 
 834 /* This is rather simplistic right now, but better than nothing. */
 835 TRef LJ_FASTCALL lj_opt_fwd_tab_len(jit_State *J)
 836 {
 837   IRRef tab = fins->op1;  /* Table reference. */
 838   IRRef lim = tab;  /* Search limit. */
 839   IRRef ref;
 840 
 841   /* Any ASTORE is a conflict and limits the search. */
 842   if (J->chain[IR_ASTORE] > lim) lim = J->chain[IR_ASTORE];
 843 
 844   /* Search for conflicting HSTORE with numeric key. */
 845   ref = J->chain[IR_HSTORE];
 846   while (ref > lim) {
 847     IRIns *store = IR(ref);
 848     IRIns *href = IR(store->op1);
 849     IRIns *key = IR(href->op2);
 850     if (irt_isnum(key->o == IR_KSLOT ? IR(key->op1)->t : key->t)) {
 851       lim = ref;  /* Conflicting store found, limits search for TLEN. */
 852       break;
 853     }
 854     ref = store->prev;
 855   }
 856 
 857   /* Try to find a matching load. Below the conflicting store, if any. */
 858   return lj_opt_cselim(J, lim);
 859 }
 860 
 861 /* -- ASTORE/HSTORE previous type analysis -------------------------------- */
 862 
 863 /* Check whether the previous value for a table store is non-nil.
 864 ** This can be derived either from a previous store or from a previous
 865 ** load (because all loads from tables perform a type check).
 866 **
 867 ** The result of the analysis can be used to avoid the metatable check
 868 ** and the guard against HREF returning niltv. Both of these are cheap,
 869 ** so let's not spend too much effort on the analysis.
 870 **
 871 ** A result of 1 is exact: previous value CANNOT be nil.
 872 ** A result of 0 is inexact: previous value MAY be nil.
 873 */
 874 int lj_opt_fwd_wasnonnil(jit_State *J, IROpT loadop, IRRef xref)
 875 {
 876   /* First check stores. */
 877   IRRef ref = J->chain[loadop+IRDELTA_L2S];
 878   while (ref > xref) {
 879     IRIns *store = IR(ref);
 880     if (store->op1 == xref) {  /* Same xREF. */
 881       /* A nil store MAY alias, but a non-nil store MUST alias. */
 882       return !irt_isnil(store->t);
 883     } else if (irt_isnil(store->t)) {  /* Must check any nil store. */
 884       IRRef skref = IR(store->op1)->op2;
 885       IRRef xkref = IR(xref)->op2;
 886       /* Same key type MAY alias. Need ALOAD check due to multiple int types. */
 887       if (loadop == IR_ALOAD || irt_sametype(IR(skref)->t, IR(xkref)->t)) {
 888         if (skref == xkref || !irref_isk(skref) || !irref_isk(xkref))
 889           return 0;  /* A nil store with same const key or var key MAY alias. */
 890         /* Different const keys CANNOT alias. */
 891       }  /* Different key types CANNOT alias. */
 892     }  /* Other non-nil stores MAY alias. */
 893     ref = store->prev;
 894   }
 895 
 896   /* Check loads since nothing could be derived from stores. */
 897   ref = J->chain[loadop];
 898   while (ref > xref) {
 899     IRIns *load = IR(ref);
 900     if (load->op1 == xref) {  /* Same xREF. */
 901       /* A nil load MAY alias, but a non-nil load MUST alias. */
 902       return !irt_isnil(load->t);
 903     }  /* Other non-nil loads MAY alias. */
 904     ref = load->prev;
 905   }
 906   return 0;  /* Nothing derived at all, previous value MAY be nil. */
 907 }
 908 
 909 /* ------------------------------------------------------------------------ */
 910 
 911 #undef IR
 912 #undef fins
 913 #undef fleft
 914 #undef fright
 915 
 916 #endif

/* [<][>][^][v][top][bottom][index][help] */