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-2012 Mike Pall. See Copyright Notice in luajit.h
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 fright (&J->fold.right)
27 ** Caveat #1: return value is not always a TRef -- only use with tref_ref().
28 ** Caveat #2: FWD relies on active CSE for xREF operands -- see lj_opt_fold().
31 /* Return values from alias analysis. */
33 ALIAS_NO
, /* The two refs CANNOT alias (exact). */
34 ALIAS_MAY
, /* The two refs MAY alias (inexact). */
35 ALIAS_MUST
/* The two refs MUST alias (exact). */
38 /* -- ALOAD/HLOAD forwarding and ASTORE/HSTORE elimination ---------------- */
40 /* Simplified escape analysis: check for intervening stores. */
41 static AliasRet
aa_escape(jit_State
*J
, IRIns
*ir
, IRIns
*stop
)
43 IRRef ref
= (IRRef
)(ir
- J
->cur
.ir
); /* The ref that might be stored. */
44 for (ir
++; ir
< stop
; ir
++)
46 (ir
->o
== IR_ASTORE
|| ir
->o
== IR_HSTORE
||
47 ir
->o
== IR_USTORE
|| ir
->o
== IR_FSTORE
))
48 return ALIAS_MAY
; /* Reference was stored and might alias. */
49 return ALIAS_NO
; /* Reference was not stored. */
52 /* Alias analysis for two different table references. */
53 static AliasRet
aa_table(jit_State
*J
, IRRef ta
, IRRef tb
)
55 IRIns
*taba
= IR(ta
), *tabb
= IR(tb
);
58 lua_assert(irt_istab(taba
->t
) && irt_istab(tabb
->t
));
59 /* Disambiguate new allocations. */
60 newa
= (taba
->o
== IR_TNEW
|| taba
->o
== IR_TDUP
);
61 newb
= (tabb
->o
== IR_TNEW
|| tabb
->o
== IR_TDUP
);
63 return ALIAS_NO
; /* Two different allocations never alias. */
64 if (newb
) { /* At least one allocation? */
65 IRIns
*tmp
= taba
; taba
= tabb
; tabb
= tmp
;
67 return ALIAS_MAY
; /* Anything else: we just don't know. */
69 return aa_escape(J
, taba
, tabb
);
72 /* Alias analysis for array and hash access using key-based disambiguation. */
73 static AliasRet
aa_ahref(jit_State
*J
, IRIns
*refa
, IRIns
*refb
)
80 return ALIAS_MUST
; /* Shortcut for same refs. */
82 if (keya
->o
== IR_KSLOT
) { ka
= keya
->op1
; keya
= IR(ka
); }
84 if (keyb
->o
== IR_KSLOT
) { kb
= keyb
->op1
; keyb
= IR(kb
); }
85 ta
= (refa
->o
==IR_HREFK
|| refa
->o
==IR_AREF
) ? IR(refa
->op1
)->op1
: refa
->op1
;
86 tb
= (refb
->o
==IR_HREFK
|| refb
->o
==IR_AREF
) ? IR(refb
->op1
)->op1
: refb
->op1
;
88 /* Same key. Check for same table with different ref (NEWREF vs. HREF). */
90 return ALIAS_MUST
; /* Same key, same table. */
92 return aa_table(J
, ta
, tb
); /* Same key, possibly different table. */
94 if (irref_isk(ka
) && irref_isk(kb
))
95 return ALIAS_NO
; /* Different constant keys. */
96 if (refa
->o
== IR_AREF
) {
97 /* Disambiguate array references based on index arithmetic. */
98 int32_t ofsa
= 0, ofsb
= 0;
99 IRRef basea
= ka
, baseb
= kb
;
100 lua_assert(refb
->o
== IR_AREF
);
101 /* Gather base and offset from t[base] or t[base+-ofs]. */
102 if (keya
->o
== IR_ADD
&& irref_isk(keya
->op2
)) {
104 ofsa
= IR(keya
->op2
)->i
;
105 if (basea
== kb
&& ofsa
!= 0)
106 return ALIAS_NO
; /* t[base+-ofs] vs. t[base]. */
108 if (keyb
->o
== IR_ADD
&& irref_isk(keyb
->op2
)) {
110 ofsb
= IR(keyb
->op2
)->i
;
111 if (ka
== baseb
&& ofsb
!= 0)
112 return ALIAS_NO
; /* t[base] vs. t[base+-ofs]. */
114 if (basea
== baseb
&& ofsa
!= ofsb
)
115 return ALIAS_NO
; /* t[base+-o1] vs. t[base+-o2] and o1 != o2. */
117 /* Disambiguate hash references based on the type of their keys. */
118 lua_assert((refa
->o
==IR_HREF
|| refa
->o
==IR_HREFK
|| refa
->o
==IR_NEWREF
) &&
119 (refb
->o
==IR_HREF
|| refb
->o
==IR_HREFK
|| refb
->o
==IR_NEWREF
));
120 if (!irt_sametype(keya
->t
, keyb
->t
))
121 return ALIAS_NO
; /* Different key types. */
124 return ALIAS_MAY
; /* Same table, cannot disambiguate keys. */
126 return aa_table(J
, ta
, tb
); /* Try to disambiguate tables. */
129 /* Array and hash load forwarding. */
130 static TRef
fwd_ahload(jit_State
*J
, IRRef xref
)
132 IRIns
*xr
= IR(xref
);
133 IRRef lim
= xref
; /* Search limit. */
136 /* Search for conflicting stores. */
137 ref
= J
->chain
[fins
->o
+IRDELTA_L2S
];
139 IRIns
*store
= IR(ref
);
140 switch (aa_ahref(J
, xr
, IR(store
->op1
))) {
141 case ALIAS_NO
: break; /* Continue searching. */
142 case ALIAS_MAY
: lim
= ref
; goto cselim
; /* Limit search for load. */
143 case ALIAS_MUST
: return store
->op2
; /* Store forwarding. */
148 /* No conflicting store (yet): const-fold loads from allocations. */
150 IRIns
*ir
= (xr
->o
== IR_HREFK
|| xr
->o
== IR_AREF
) ? IR(xr
->op1
) : xr
;
153 if (ir
->o
== IR_TNEW
|| (ir
->o
== IR_TDUP
&& irref_isk(xr
->op2
))) {
154 /* A NEWREF with a number key may end up pointing to the array part.
155 ** But it's referenced from HSTORE and not found in the ASTORE chain.
156 ** For now simply consider this a conflict without forwarding anything.
158 if (xr
->o
== IR_AREF
) {
159 IRRef ref2
= J
->chain
[IR_NEWREF
];
161 IRIns
*newref
= IR(ref2
);
162 if (irt_isnum(IR(newref
->op2
)->t
))
167 /* NEWREF inhibits CSE for HREF, and dependent FLOADs from HREFK/AREF.
168 ** But the above search for conflicting stores was limited by xref.
169 ** So continue searching, limited by the TNEW/TDUP. Store forwarding
170 ** is ok, too. A conflict does NOT limit the search for a matching load.
173 IRIns
*store
= IR(ref
);
174 switch (aa_ahref(J
, xr
, IR(store
->op1
))) {
175 case ALIAS_NO
: break; /* Continue searching. */
176 case ALIAS_MAY
: goto cselim
; /* Conflicting store. */
177 case ALIAS_MUST
: return store
->op2
; /* Store forwarding. */
181 lua_assert(ir
->o
!= IR_TNEW
|| irt_isnil(fins
->t
));
182 if (irt_ispri(fins
->t
)) {
183 return TREF_PRI(irt_type(fins
->t
));
184 } else if (irt_isnum(fins
->t
) || irt_isstr(fins
->t
)) {
187 IRIns
*key
= IR(xr
->op2
);
188 if (key
->o
== IR_KSLOT
) key
= IR(key
->op1
);
189 lj_ir_kvalue(J
->L
, &keyv
, key
);
190 tv
= lj_tab_get(J
->L
, ir_ktab(IR(ir
->op1
)), &keyv
);
191 lua_assert(itype2irt(tv
) == irt_type(fins
->t
));
192 if (irt_isnum(fins
->t
))
193 return lj_ir_knum_u64(J
, tv
->u64
);
195 return lj_ir_kstr(J
, strV(tv
));
197 /* Othwerwise: don't intern as a constant. */
202 /* Try to find a matching load. Below the conflicting store, if any. */
203 ref
= J
->chain
[fins
->o
];
205 IRIns
*load
= IR(ref
);
206 if (load
->op1
== xref
)
207 return ref
; /* Load forwarding. */
210 return 0; /* Conflict or no match. */
213 /* Reassociate ALOAD across PHIs to handle t[i-1] forwarding case. */
214 static TRef
fwd_aload_reassoc(jit_State
*J
)
216 IRIns
*irx
= IR(fins
->op1
);
217 IRIns
*key
= IR(irx
->op2
);
218 if (key
->o
== IR_ADD
&& irref_isk(key
->op2
)) {
219 IRIns
*add2
= IR(key
->op1
);
220 if (add2
->o
== IR_ADD
&& irref_isk(add2
->op2
) &&
221 IR(key
->op2
)->i
== -IR(add2
->op2
)->i
) {
222 IRRef ref
= J
->chain
[IR_AREF
];
223 IRRef lim
= add2
->op1
;
224 if (irx
->op1
> lim
) lim
= irx
->op1
;
227 if (ir
->op1
== irx
->op1
&& ir
->op2
== add2
->op1
)
228 return fwd_ahload(J
, ref
);
236 /* ALOAD forwarding. */
237 TRef LJ_FASTCALL
lj_opt_fwd_aload(jit_State
*J
)
240 if ((ref
= fwd_ahload(J
, fins
->op1
)) ||
241 (ref
= fwd_aload_reassoc(J
)))
246 /* HLOAD forwarding. */
247 TRef LJ_FASTCALL
lj_opt_fwd_hload(jit_State
*J
)
249 IRRef ref
= fwd_ahload(J
, fins
->op1
);
255 /* Check whether HREF of TNEW/TDUP can be folded to niltv. */
256 int LJ_FASTCALL
lj_opt_fwd_href_nokey(jit_State
*J
)
258 IRRef lim
= fins
->op1
; /* Search limit. */
261 /* The key for an ASTORE may end up in the hash part after a NEWREF. */
262 if (irt_isnum(fright
->t
) && J
->chain
[IR_NEWREF
] > lim
) {
263 ref
= J
->chain
[IR_ASTORE
];
265 if (ref
< J
->chain
[IR_NEWREF
])
266 return 0; /* Conflict. */
271 /* Search for conflicting stores. */
272 ref
= J
->chain
[IR_HSTORE
];
274 IRIns
*store
= IR(ref
);
275 if (aa_ahref(J
, fins
, IR(store
->op1
)) != ALIAS_NO
)
276 return 0; /* Conflict. */
280 return 1; /* No conflict. Can fold to niltv. */
283 /* Check whether there's no aliasing NEWREF for the left operand. */
284 int LJ_FASTCALL
lj_opt_fwd_tptr(jit_State
*J
, IRRef lim
)
286 IRRef ta
= fins
->op1
;
287 IRRef ref
= J
->chain
[IR_NEWREF
];
289 IRIns
*newref
= IR(ref
);
290 if (ta
== newref
->op1
|| aa_table(J
, ta
, newref
->op1
) != ALIAS_NO
)
291 return 0; /* Conflict. */
294 return 1; /* No conflict. Can safely FOLD/CSE. */
297 /* ASTORE/HSTORE elimination. */
298 TRef LJ_FASTCALL
lj_opt_dse_ahstore(jit_State
*J
)
300 IRRef xref
= fins
->op1
; /* xREF reference. */
301 IRRef val
= fins
->op2
; /* Stored value reference. */
302 IRIns
*xr
= IR(xref
);
303 IRRef1
*refp
= &J
->chain
[fins
->o
];
305 while (ref
> xref
) { /* Search for redundant or conflicting stores. */
306 IRIns
*store
= IR(ref
);
307 switch (aa_ahref(J
, xr
, IR(store
->op1
))) {
309 break; /* Continue searching. */
310 case ALIAS_MAY
: /* Store to MAYBE the same location. */
311 if (store
->op2
!= val
) /* Conflict if the value is different. */
313 break; /* Otherwise continue searching. */
314 case ALIAS_MUST
: /* Store to the same location. */
315 if (store
->op2
== val
) /* Same value: drop the new store. */
317 /* Different value: try to eliminate the redundant store. */
318 if (ref
> J
->chain
[IR_LOOP
]) { /* Quick check to avoid crossing LOOP. */
320 /* Check for any intervening guards (includes conflicting loads). */
321 for (ir
= IR(J
->cur
.nins
-1); ir
> store
; ir
--)
322 if (irt_isguard(ir
->t
))
323 goto doemit
; /* No elimination possible. */
324 /* Remove redundant store from chain and replace with NOP. */
327 store
->t
.irt
= IRT_NIL
;
328 store
->op1
= store
->op2
= 0;
330 /* Now emit the new store instead. */
334 ref
= *(refp
= &store
->prev
);
337 return EMITFOLD
; /* Otherwise we have a conflict or simply no match. */
340 /* -- ULOAD forwarding ---------------------------------------------------- */
342 /* The current alias analysis for upvalues is very simplistic. It only
343 ** disambiguates between the unique upvalues of the same function.
344 ** This is good enough for now, since most upvalues are read-only.
346 ** A more precise analysis would be feasible with the help of the parser:
347 ** generate a unique key for every upvalue, even across all prototypes.
348 ** Lacking a realistic use-case, it's unclear whether this is beneficial.
350 static AliasRet
aa_uref(IRIns
*refa
, IRIns
*refb
)
352 if (refa
->o
!= refb
->o
)
353 return ALIAS_NO
; /* Different UREFx type. */
354 if (refa
->op1
== refb
->op1
) { /* Same function. */
355 if (refa
->op2
== refb
->op2
)
356 return ALIAS_MUST
; /* Same function, same upvalue idx. */
358 return ALIAS_NO
; /* Same function, different upvalue idx. */
359 } else { /* Different functions, check disambiguation hash values. */
360 if (((refa
->op2
^ refb
->op2
) & 0xff))
361 return ALIAS_NO
; /* Upvalues with different hash values cannot alias. */
363 return ALIAS_MAY
; /* No conclusion can be drawn for same hash value. */
367 /* ULOAD forwarding. */
368 TRef LJ_FASTCALL
lj_opt_fwd_uload(jit_State
*J
)
370 IRRef uref
= fins
->op1
;
371 IRRef lim
= uref
; /* Search limit. */
372 IRIns
*xr
= IR(uref
);
375 /* Search for conflicting stores. */
376 ref
= J
->chain
[IR_USTORE
];
378 IRIns
*store
= IR(ref
);
379 switch (aa_uref(xr
, IR(store
->op1
))) {
380 case ALIAS_NO
: break; /* Continue searching. */
381 case ALIAS_MAY
: lim
= ref
; goto cselim
; /* Limit search for load. */
382 case ALIAS_MUST
: return store
->op2
; /* Store forwarding. */
388 /* Try to find a matching load. Below the conflicting store, if any. */
389 return lj_opt_cselim(J
, lim
);
392 /* USTORE elimination. */
393 TRef LJ_FASTCALL
lj_opt_dse_ustore(jit_State
*J
)
395 IRRef xref
= fins
->op1
; /* xREF reference. */
396 IRRef val
= fins
->op2
; /* Stored value reference. */
397 IRIns
*xr
= IR(xref
);
398 IRRef1
*refp
= &J
->chain
[IR_USTORE
];
400 while (ref
> xref
) { /* Search for redundant or conflicting stores. */
401 IRIns
*store
= IR(ref
);
402 switch (aa_uref(xr
, IR(store
->op1
))) {
404 break; /* Continue searching. */
405 case ALIAS_MAY
: /* Store to MAYBE the same location. */
406 if (store
->op2
!= val
) /* Conflict if the value is different. */
408 break; /* Otherwise continue searching. */
409 case ALIAS_MUST
: /* Store to the same location. */
410 if (store
->op2
== val
) /* Same value: drop the new store. */
412 /* Different value: try to eliminate the redundant store. */
413 if (ref
> J
->chain
[IR_LOOP
]) { /* Quick check to avoid crossing LOOP. */
415 /* Check for any intervening guards (includes conflicting loads). */
416 for (ir
= IR(J
->cur
.nins
-1); ir
> store
; ir
--)
417 if (irt_isguard(ir
->t
))
418 goto doemit
; /* No elimination possible. */
419 /* Remove redundant store from chain and replace with NOP. */
422 store
->t
.irt
= IRT_NIL
;
423 store
->op1
= store
->op2
= 0;
425 if (ref
+1 < J
->cur
.nins
&&
426 store
[1].o
== IR_OBAR
&& store
[1].op1
== xref
) {
427 IRRef1
*bp
= &J
->chain
[IR_OBAR
];
429 for (obar
= IR(*bp
); *bp
> ref
+1; obar
= IR(*bp
))
431 /* Remove OBAR, too. */
434 obar
->t
.irt
= IRT_NIL
;
435 obar
->op1
= obar
->op2
= 0;
438 /* Now emit the new store instead. */
442 ref
= *(refp
= &store
->prev
);
445 return EMITFOLD
; /* Otherwise we have a conflict or simply no match. */
448 /* -- FLOAD forwarding and FSTORE elimination ----------------------------- */
450 /* Alias analysis for field access.
451 ** Field loads are cheap and field stores are rare.
452 ** Simple disambiguation based on field types is good enough.
454 static AliasRet
aa_fref(jit_State
*J
, IRIns
*refa
, IRIns
*refb
)
456 if (refa
->op2
!= refb
->op2
)
457 return ALIAS_NO
; /* Different fields. */
458 if (refa
->op1
== refb
->op1
)
459 return ALIAS_MUST
; /* Same field, same object. */
460 else if (refa
->op2
>= IRFL_TAB_META
&& refa
->op2
<= IRFL_TAB_NOMM
)
461 return aa_table(J
, refa
->op1
, refb
->op1
); /* Disambiguate tables. */
463 return ALIAS_MAY
; /* Same field, possibly different object. */
466 /* Only the loads for mutable fields end up here (see FOLD). */
467 TRef LJ_FASTCALL
lj_opt_fwd_fload(jit_State
*J
)
469 IRRef oref
= fins
->op1
; /* Object reference. */
470 IRRef fid
= fins
->op2
; /* Field ID. */
471 IRRef lim
= oref
; /* Search limit. */
474 /* Search for conflicting stores. */
475 ref
= J
->chain
[IR_FSTORE
];
477 IRIns
*store
= IR(ref
);
478 switch (aa_fref(J
, fins
, IR(store
->op1
))) {
479 case ALIAS_NO
: break; /* Continue searching. */
480 case ALIAS_MAY
: lim
= ref
; goto cselim
; /* Limit search for load. */
481 case ALIAS_MUST
: return store
->op2
; /* Store forwarding. */
486 /* No conflicting store: const-fold field loads from allocations. */
487 if (fid
== IRFL_TAB_META
) {
488 IRIns
*ir
= IR(oref
);
489 if (ir
->o
== IR_TNEW
|| ir
->o
== IR_TDUP
)
490 return lj_ir_knull(J
, IRT_TAB
);
494 /* Try to find a matching load. Below the conflicting store, if any. */
495 return lj_opt_cselim(J
, lim
);
498 /* FSTORE elimination. */
499 TRef LJ_FASTCALL
lj_opt_dse_fstore(jit_State
*J
)
501 IRRef fref
= fins
->op1
; /* FREF reference. */
502 IRRef val
= fins
->op2
; /* Stored value reference. */
503 IRIns
*xr
= IR(fref
);
504 IRRef1
*refp
= &J
->chain
[IR_FSTORE
];
506 while (ref
> fref
) { /* Search for redundant or conflicting stores. */
507 IRIns
*store
= IR(ref
);
508 switch (aa_fref(J
, xr
, IR(store
->op1
))) {
510 break; /* Continue searching. */
512 if (store
->op2
!= val
) /* Conflict if the value is different. */
514 break; /* Otherwise continue searching. */
516 if (store
->op2
== val
) /* Same value: drop the new store. */
518 /* Different value: try to eliminate the redundant store. */
519 if (ref
> J
->chain
[IR_LOOP
]) { /* Quick check to avoid crossing LOOP. */
521 /* Check for any intervening guards or conflicting loads. */
522 for (ir
= IR(J
->cur
.nins
-1); ir
> store
; ir
--)
523 if (irt_isguard(ir
->t
) || (ir
->o
== IR_FLOAD
&& ir
->op2
== xr
->op2
))
524 goto doemit
; /* No elimination possible. */
525 /* Remove redundant store from chain and replace with NOP. */
528 store
->t
.irt
= IRT_NIL
;
529 store
->op1
= store
->op2
= 0;
531 /* Now emit the new store instead. */
535 ref
= *(refp
= &store
->prev
);
538 return EMITFOLD
; /* Otherwise we have a conflict or simply no match. */
541 /* -- XLOAD forwarding and XSTORE elimination ----------------------------- */
543 /* Find cdata allocation for a reference (if any). */
544 static IRIns
*aa_findcnew(jit_State
*J
, IRIns
*ir
)
546 while (ir
->o
== IR_ADD
) {
547 if (!irref_isk(ir
->op1
)) {
548 IRIns
*ir1
= aa_findcnew(J
, IR(ir
->op1
)); /* Left-recursion. */
551 if (irref_isk(ir
->op2
)) return NULL
;
552 ir
= IR(ir
->op2
); /* Flatten right-recursion. */
554 return ir
->o
== IR_CNEW
? ir
: NULL
;
557 /* Alias analysis for two cdata allocations. */
558 static AliasRet
aa_cnew(jit_State
*J
, IRIns
*refa
, IRIns
*refb
)
560 IRIns
*cnewa
= aa_findcnew(J
, refa
);
561 IRIns
*cnewb
= aa_findcnew(J
, refb
);
563 return ALIAS_MAY
; /* Same allocation or neither is an allocation. */
565 return ALIAS_NO
; /* Two different allocations never alias. */
566 if (cnewb
) { cnewa
= cnewb
; refb
= refa
; }
567 return aa_escape(J
, cnewa
, refb
);
570 /* Alias analysis for XLOAD/XSTORE. */
571 static AliasRet
aa_xref(jit_State
*J
, IRIns
*refa
, IRIns
*xa
, IRIns
*xb
)
573 ptrdiff_t ofsa
= 0, ofsb
= 0;
574 IRIns
*refb
= IR(xb
->op1
);
575 IRIns
*basea
= refa
, *baseb
= refb
;
576 /* This implements (very) strict aliasing rules.
577 ** Different types do NOT alias, except for differences in signedness.
578 ** NYI: this also prevents type punning through unions.
580 if (irt_sametype(xa
->t
, xb
->t
)) {
582 return ALIAS_MUST
; /* Shortcut for same refs with identical type. */
583 } else if (!(irt_typerange(xa
->t
, IRT_I8
, IRT_U64
) &&
584 ((xa
->t
.irt
- IRT_I8
) ^ (xb
->t
.irt
- IRT_I8
)) == 1)) {
587 /* Offset-based disambiguation. */
588 if (refa
->o
== IR_ADD
&& irref_isk(refa
->op2
)) {
589 IRIns
*irk
= IR(refa
->op2
);
590 basea
= IR(refa
->op1
);
591 ofsa
= (LJ_64
&& irk
->o
== IR_KINT64
) ? (ptrdiff_t)ir_k64(irk
)->u64
:
593 if (basea
== refb
&& ofsa
!= 0)
594 return ALIAS_NO
; /* base+-ofs vs. base. */
596 if (refb
->o
== IR_ADD
&& irref_isk(refb
->op2
)) {
597 IRIns
*irk
= IR(refb
->op2
);
598 baseb
= IR(refb
->op1
);
599 ofsb
= (LJ_64
&& irk
->o
== IR_KINT64
) ? (ptrdiff_t)ir_k64(irk
)->u64
:
601 if (refa
== baseb
&& ofsb
!= 0)
602 return ALIAS_NO
; /* base vs. base+-ofs. */
604 if (basea
== baseb
) {
605 /* This assumes strictly-typed, non-overlapping accesses. */
607 return ALIAS_NO
; /* base+-o1 vs. base+-o2 and o1 != o2. */
608 return ALIAS_MUST
; /* Unsigned vs. signed access to the same address. */
610 /* NYI: structural disambiguation. */
611 return aa_cnew(J
, basea
, baseb
); /* Try to disambiguate allocations. */
614 /* Return CSEd reference or 0. Caveat: swaps lower ref to the right! */
615 static IRRef
reassoc_trycse(jit_State
*J
, IROp op
, IRRef op1
, IRRef op2
)
617 IRRef ref
= J
->chain
[op
];
619 if (op2
> lim
) { lim
= op2
; op2
= op1
; op1
= lim
; }
622 if (ir
->op1
== op1
&& ir
->op2
== op2
)
629 /* Reassociate index references. */
630 static IRRef
reassoc_xref(jit_State
*J
, IRIns
*ir
)
633 if (ir
->o
== IR_ADD
&& irref_isk(ir
->op2
)) { /* Get constant offset. */
634 IRIns
*irk
= IR(ir
->op2
);
635 ofs
= (LJ_64
&& irk
->o
== IR_KINT64
) ? (ptrdiff_t)ir_k64(irk
)->u64
:
639 if (ir
->o
== IR_ADD
) { /* Add of base + index. */
640 /* Index ref > base ref for loop-carried dependences. Only check op1. */
641 IRIns
*ir2
, *ir1
= IR(ir
->op1
);
644 /* Determine index shifts. Don't bother with IR_MUL here. */
645 if (ir1
->o
== IR_BSHL
&& irref_isk(ir1
->op2
))
646 shift
= IR(ir1
->op2
)->i
;
647 else if (ir1
->o
== IR_ADD
&& ir1
->op1
== ir1
->op2
)
652 /* A non-reassociated add. Must be a loop-carried dependence. */
653 if (ir2
->o
== IR_ADD
&& irt_isint(ir2
->t
) && irref_isk(ir2
->op2
))
654 ofs
+= (ptrdiff_t)IR(ir2
->op2
)->i
<< shift
;
658 /* Try to CSE the reassociated chain. Give up if not found. */
660 !(idxref
= reassoc_trycse(J
, ir1
->o
, idxref
,
661 ir1
->o
== IR_BSHL
? ir1
->op2
: idxref
)))
663 if (!(idxref
= reassoc_trycse(J
, IR_ADD
, idxref
, ir
->op2
)))
666 IRRef refk
= tref_ref(lj_ir_kintp(J
, ofs
));
667 if (!(idxref
= reassoc_trycse(J
, IR_ADD
, idxref
, refk
)))
670 return idxref
; /* Success, found a reassociated index reference. Phew. */
672 return 0; /* Failure. */
675 /* XLOAD forwarding. */
676 TRef LJ_FASTCALL
lj_opt_fwd_xload(jit_State
*J
)
678 IRRef xref
= fins
->op1
;
679 IRIns
*xr
= IR(xref
);
680 IRRef lim
= xref
; /* Search limit. */
683 if ((fins
->op2
& IRXLOAD_READONLY
))
685 if ((fins
->op2
& IRXLOAD_VOLATILE
))
688 /* Search for conflicting stores. */
689 ref
= J
->chain
[IR_XSTORE
];
691 if (J
->chain
[IR_CALLXS
] > lim
) lim
= J
->chain
[IR_CALLXS
];
692 if (J
->chain
[IR_XBAR
] > lim
) lim
= J
->chain
[IR_XBAR
];
694 IRIns
*store
= IR(ref
);
695 switch (aa_xref(J
, xr
, fins
, store
)) {
696 case ALIAS_NO
: break; /* Continue searching. */
697 case ALIAS_MAY
: lim
= ref
; goto cselim
; /* Limit search for load. */
699 /* Emit conversion if the loaded type doesn't match the forwarded type. */
700 if (!irt_sametype(fins
->t
, IR(store
->op2
)->t
)) {
701 IRType st
= irt_type(fins
->t
);
702 if (st
== IRT_I8
|| st
== IRT_I16
) { /* Trunc + sign-extend. */
704 } else if (st
== IRT_U8
|| st
== IRT_U16
) { /* Trunc + zero-extend. */
705 } else if (st
== IRT_INT
&& !irt_isint(IR(store
->op2
)->t
)) {
706 st
= irt_type(IR(store
->op2
)->t
); /* Needs dummy CONV.int.*. */
707 } else { /* I64/U64 are boxed, U32 is hidden behind a CONV.num.u32. */
710 fins
->ot
= IRTI(IR_CONV
);
711 fins
->op1
= store
->op2
;
712 fins
->op2
= (IRT_INT
<<5)|st
;
716 return store
->op2
; /* Store forwarding. */
722 /* Try to find a matching load. Below the conflicting store, if any. */
723 ref
= J
->chain
[IR_XLOAD
];
725 /* CSE for XLOAD depends on the type, but not on the IRXLOAD_* flags. */
726 if (IR(ref
)->op1
== xref
&& irt_sametype(IR(ref
)->t
, fins
->t
))
731 /* Reassociate XLOAD across PHIs to handle a[i-1] forwarding case. */
732 if (!(fins
->op2
& IRXLOAD_READONLY
) && J
->chain
[IR_LOOP
] &&
733 xref
== fins
->op1
&& (xref
= reassoc_xref(J
, xr
)) != 0) {
734 ref
= J
->chain
[IR_XSTORE
];
735 while (ref
> lim
) /* Skip stores that have already been checked. */
739 goto retry
; /* Retry with the reassociated reference. */
745 /* XSTORE elimination. */
746 TRef LJ_FASTCALL
lj_opt_dse_xstore(jit_State
*J
)
748 IRRef xref
= fins
->op1
;
749 IRIns
*xr
= IR(xref
);
750 IRRef lim
= xref
; /* Search limit. */
751 IRRef val
= fins
->op2
; /* Stored value reference. */
752 IRRef1
*refp
= &J
->chain
[IR_XSTORE
];
754 if (J
->chain
[IR_CALLXS
] > lim
) lim
= J
->chain
[IR_CALLXS
];
755 if (J
->chain
[IR_XBAR
] > lim
) lim
= J
->chain
[IR_XBAR
];
756 while (ref
> lim
) { /* Search for redundant or conflicting stores. */
757 IRIns
*store
= IR(ref
);
758 switch (aa_xref(J
, xr
, fins
, store
)) {
760 break; /* Continue searching. */
762 if (store
->op2
!= val
) /* Conflict if the value is different. */
764 break; /* Otherwise continue searching. */
766 if (store
->op2
== val
) /* Same value: drop the new store. */
768 /* Different value: try to eliminate the redundant store. */
769 if (ref
> J
->chain
[IR_LOOP
]) { /* Quick check to avoid crossing LOOP. */
771 /* Check for any intervening guards or any XLOADs (no AA performed). */
772 for (ir
= IR(J
->cur
.nins
-1); ir
> store
; ir
--)
773 if (irt_isguard(ir
->t
) || ir
->o
== IR_XLOAD
)
774 goto doemit
; /* No elimination possible. */
775 /* Remove redundant store from chain and replace with NOP. */
778 store
->t
.irt
= IRT_NIL
;
779 store
->op1
= store
->op2
= 0;
781 /* Now emit the new store instead. */
785 ref
= *(refp
= &store
->prev
);
788 return EMITFOLD
; /* Otherwise we have a conflict or simply no match. */
791 /* -- Forwarding of lj_tab_len -------------------------------------------- */
793 /* This is rather simplistic right now, but better than nothing. */
794 TRef LJ_FASTCALL
lj_opt_fwd_tab_len(jit_State
*J
)
796 IRRef tab
= fins
->op1
; /* Table reference. */
797 IRRef lim
= tab
; /* Search limit. */
800 /* Any ASTORE is a conflict and limits the search. */
801 if (J
->chain
[IR_ASTORE
] > lim
) lim
= J
->chain
[IR_ASTORE
];
803 /* Search for conflicting HSTORE with numeric key. */
804 ref
= J
->chain
[IR_HSTORE
];
806 IRIns
*store
= IR(ref
);
807 IRIns
*href
= IR(store
->op1
);
808 IRIns
*key
= IR(href
->op2
);
809 if (irt_isnum(key
->o
== IR_KSLOT
? IR(key
->op1
)->t
: key
->t
)) {
810 lim
= ref
; /* Conflicting store found, limits search for TLEN. */
816 /* Try to find a matching load. Below the conflicting store, if any. */
817 return lj_opt_cselim(J
, lim
);
820 /* -- ASTORE/HSTORE previous type analysis -------------------------------- */
822 /* Check whether the previous value for a table store is non-nil.
823 ** This can be derived either from a previous store or from a previous
824 ** load (because all loads from tables perform a type check).
826 ** The result of the analysis can be used to avoid the metatable check
827 ** and the guard against HREF returning niltv. Both of these are cheap,
828 ** so let's not spend too much effort on the analysis.
830 ** A result of 1 is exact: previous value CANNOT be nil.
831 ** A result of 0 is inexact: previous value MAY be nil.
833 int lj_opt_fwd_wasnonnil(jit_State
*J
, IROpT loadop
, IRRef xref
)
835 /* First check stores. */
836 IRRef ref
= J
->chain
[loadop
+IRDELTA_L2S
];
838 IRIns
*store
= IR(ref
);
839 if (store
->op1
== xref
) { /* Same xREF. */
840 /* A nil store MAY alias, but a non-nil store MUST alias. */
841 return !irt_isnil(store
->t
);
842 } else if (irt_isnil(store
->t
)) { /* Must check any nil store. */
843 IRRef skref
= IR(store
->op1
)->op2
;
844 IRRef xkref
= IR(xref
)->op2
;
845 /* Same key type MAY alias. Need ALOAD check due to multiple int types. */
846 if (loadop
== IR_ALOAD
|| irt_sametype(IR(skref
)->t
, IR(xkref
)->t
)) {
847 if (skref
== xkref
|| !irref_isk(skref
) || !irref_isk(xkref
))
848 return 0; /* A nil store with same const key or var key MAY alias. */
849 /* Different const keys CANNOT alias. */
850 } /* Different key types CANNOT alias. */
851 } /* Other non-nil stores MAY alias. */
855 /* Check loads since nothing could be derived from stores. */
856 ref
= J
->chain
[loadop
];
858 IRIns
*load
= IR(ref
);
859 if (load
->op1
== xref
) { /* Same xREF. */
860 /* A nil load MAY alias, but a non-nil load MUST alias. */
861 return !irt_isnil(load
->t
);
862 } /* Other non-nil loads MAY alias. */
865 return 0; /* Nothing derived at all, previous value MAY be nil. */
868 /* ------------------------------------------------------------------------ */