summaryrefslogtreecommitdiff
path: root/src/lj_opt_mem.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lj_opt_mem.c')
-rw-r--r--src/lj_opt_mem.c550
1 files changed, 550 insertions, 0 deletions
diff --git a/src/lj_opt_mem.c b/src/lj_opt_mem.c
new file mode 100644
index 00000000..77a9c0e7
--- /dev/null
+++ b/src/lj_opt_mem.c
@@ -0,0 +1,550 @@
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-2009 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
25/*
26** Caveat #1: return value is not always a TRef -- only use with tref_ref().
27** Caveat #2: FWD relies on active CSE for xREF operands -- see lj_opt_fold().
28*/
29
30/* Return values from alias analysis. */
31typedef enum {
32 ALIAS_NO, /* The two refs CANNOT alias (exact). */
33 ALIAS_MAY, /* The two refs MAY alias (inexact). */
34 ALIAS_MUST /* The two refs MUST alias (exact). */
35} AliasRet;
36
37/* -- ALOAD/HLOAD forwarding and ASTORE/HSTORE elimination ---------------- */
38
39/* Alias analysis for array and hash access using key-based disambiguation. */
40static AliasRet aa_ahref(jit_State *J, IRIns *refa, IRIns *refb)
41{
42 IRRef ka = refa->op2;
43 IRRef kb = refb->op2;
44 IRIns *keya, *keyb;
45 if (refa == refb)
46 return ALIAS_MUST; /* Shortcut for same refs. */
47 keya = IR(ka);
48 if (keya->o == IR_KSLOT) { ka = keya->op1; keya = IR(ka); }
49 keyb = IR(kb);
50 if (keyb->o == IR_KSLOT) { kb = keyb->op1; keyb = IR(kb); }
51 if (ka == kb) {
52 /* Same key. Check for same table with different ref (NEWREF vs. HREF). */
53 IRIns *ta = refa;
54 IRIns *tb = refb;
55 if (ta->o == IR_HREFK || ta->o == IR_AREF) ta = IR(ta->op1);
56 if (tb->o == IR_HREFK || tb->o == IR_AREF) tb = IR(tb->op1);
57 if (ta->op1 == tb->op1)
58 return ALIAS_MUST; /* Same key, same table. */
59 else
60 return ALIAS_MAY; /* Same key, possibly different table. */
61 }
62 if (irref_isk(ka) && irref_isk(kb))
63 return ALIAS_NO; /* Different constant keys. */
64 if (refa->o == IR_AREF) {
65 /* Disambiguate array references based on index arithmetic. */
66 lua_assert(refb->o == IR_AREF);
67 if (refa->op1 == refb->op1) {
68 /* Same table, different non-const array keys. */
69 int32_t ofsa = 0, ofsb = 0;
70 IRRef basea = ka, baseb = kb;
71 /* Gather base and offset from t[base] or t[base+-ofs]. */
72 if (keya->o == IR_ADD && irref_isk(keya->op2)) {
73 basea = keya->op1;
74 ofsa = IR(keya->op2)->i;
75 if (basea == kb && ofsa != 0)
76 return ALIAS_NO; /* t[base+-ofs] vs. t[base]. */
77 }
78 if (keyb->o == IR_ADD && irref_isk(keyb->op2)) {
79 baseb = keyb->op1;
80 ofsb = IR(keyb->op2)->i;
81 if (ka == baseb && ofsb != 0)
82 return ALIAS_NO; /* t[base] vs. t[base+-ofs]. */
83 }
84 if (basea == baseb && ofsa != ofsb)
85 return ALIAS_NO; /* t[base+-o1] vs. t[base+-o2] and o1 != o2. */
86 }
87 } else {
88 /* Disambiguate hash references based on the type of their keys. */
89 lua_assert((refa->o==IR_HREF || refa->o==IR_HREFK || refa->o==IR_NEWREF) &&
90 (refb->o==IR_HREF || refb->o==IR_HREFK || refb->o==IR_NEWREF));
91 if (!irt_sametype(keya->t, keyb->t))
92 return ALIAS_NO; /* Different key types. */
93 }
94 return ALIAS_MAY; /* Anything else: we just don't know. */
95}
96
97/* Array and hash load forwarding. */
98static TRef fwd_ahload(jit_State *J, IRRef xref)
99{
100 IRIns *xr = IR(xref);
101 IRRef lim = xref; /* Search limit. */
102 IRRef ref;
103
104 /* Search for conflicting stores. */
105 ref = J->chain[fins->o+IRDELTA_L2S];
106 while (ref > xref) {
107 IRIns *store = IR(ref);
108 switch (aa_ahref(J, xr, IR(store->op1))) {
109 case ALIAS_NO: break; /* Continue searching. */
110 case ALIAS_MAY: lim = ref; goto conflict; /* Limit search for load. */
111 case ALIAS_MUST: return store->op2; /* Store forwarding. */
112 }
113 ref = store->prev;
114 }
115
116 /* No conflicting store (yet): const-fold loads from allocations. */
117 {
118 IRIns *ir = (xr->o == IR_HREFK || xr->o == IR_AREF) ? IR(xr->op1) : xr;
119 IRRef tab = ir->op1;
120 ir = IR(tab);
121 if (ir->o == IR_TNEW || (ir->o == IR_TDUP && irref_isk(xr->op2))) {
122 /* A NEWREF with a number key may end up pointing to the array part.
123 ** But it's referenced from HSTORE and not found in the ASTORE chain.
124 ** For now simply consider this a conflict without forwarding anything.
125 */
126 if (xr->o == IR_AREF) {
127 IRRef ref2 = J->chain[IR_NEWREF];
128 while (ref2 > tab) {
129 IRIns *newref = IR(ref2);
130 if (irt_isnum(IR(newref->op2)->t))
131 goto conflict;
132 ref2 = newref->prev;
133 }
134 }
135 /* NEWREF inhibits CSE for HREF, and dependent FLOADs from HREFK/AREF.
136 ** But the above search for conflicting stores was limited by xref.
137 ** So continue searching, limited by the TNEW/TDUP. Store forwarding
138 ** is ok, too. A conflict does NOT limit the search for a matching load.
139 */
140 while (ref > tab) {
141 IRIns *store = IR(ref);
142 switch (aa_ahref(J, xr, IR(store->op1))) {
143 case ALIAS_NO: break; /* Continue searching. */
144 case ALIAS_MAY: goto conflict; /* Conflicting store. */
145 case ALIAS_MUST: return store->op2; /* Store forwarding. */
146 }
147 ref = store->prev;
148 }
149 lua_assert(ir->o != IR_TNEW || irt_isnil(fins->t));
150 if (irt_ispri(fins->t)) {
151 return TREF_PRI(irt_type(fins->t));
152 } else if (irt_isnum(fins->t) || irt_isstr(fins->t)) {
153 TValue keyv;
154 cTValue *tv;
155 IRIns *key = IR(xr->op2);
156 if (key->o == IR_KSLOT) key = IR(key->op1);
157 lj_ir_kvalue(J->L, &keyv, key);
158 tv = lj_tab_get(J->L, ir_ktab(IR(ir->op1)), &keyv);
159 lua_assert(itype2irt(tv) == irt_type(fins->t));
160 if (irt_isnum(fins->t))
161 return lj_ir_knum_nn(J, tv->u64);
162 else
163 return lj_ir_kstr(J, strV(tv));
164 }
165 /* Othwerwise: don't intern as a constant. */
166 }
167 }
168
169conflict:
170 /* Try to find a matching load. Below the conflicting store, if any. */
171 ref = J->chain[fins->o];
172 while (ref > lim) {
173 IRIns *load = IR(ref);
174 if (load->op1 == xref)
175 return ref; /* Load forwarding. */
176 ref = load->prev;
177 }
178 return 0; /* Conflict or no match. */
179}
180
181/* Reassociate ALOAD across PHIs to handle t[i-1] forwarding case. */
182static TRef fwd_aload_reassoc(jit_State *J)
183{
184 IRIns *irx = IR(fins->op1);
185 IRIns *key = IR(irx->op2);
186 if (key->o == IR_ADD && irref_isk(key->op2)) {
187 IRIns *add2 = IR(key->op1);
188 if (add2->o == IR_ADD && irref_isk(add2->op2) &&
189 IR(key->op2)->i == -IR(add2->op2)->i) {
190 IRRef ref = J->chain[IR_AREF];
191 IRRef lim = add2->op1;
192 if (irx->op1 > lim) lim = irx->op1;
193 while (ref > lim) {
194 IRIns *ir = IR(ref);
195 if (ir->op1 == irx->op1 && ir->op2 == add2->op1)
196 return fwd_ahload(J, ref);
197 ref = ir->prev;
198 }
199 }
200 }
201 return 0;
202}
203
204/* ALOAD forwarding. */
205TRef LJ_FASTCALL lj_opt_fwd_aload(jit_State *J)
206{
207 IRRef ref;
208 if ((ref = fwd_ahload(J, fins->op1)) ||
209 (ref = fwd_aload_reassoc(J)))
210 return ref;
211 return EMITFOLD;
212}
213
214/* HLOAD forwarding. */
215TRef LJ_FASTCALL lj_opt_fwd_hload(jit_State *J)
216{
217 IRRef ref = fwd_ahload(J, fins->op1);
218 if (ref)
219 return ref;
220 return EMITFOLD;
221}
222
223/* ASTORE/HSTORE elimination. */
224TRef LJ_FASTCALL lj_opt_dse_ahstore(jit_State *J)
225{
226 IRRef xref = fins->op1; /* xREF reference. */
227 IRRef val = fins->op2; /* Stored value reference. */
228 IRIns *xr = IR(xref);
229 IRRef1 *refp = &J->chain[fins->o];
230 IRRef ref = *refp;
231 while (ref > xref) { /* Search for redundant or conflicting stores. */
232 IRIns *store = IR(ref);
233 switch (aa_ahref(J, xr, IR(store->op1))) {
234 case ALIAS_NO:
235 break; /* Continue searching. */
236 case ALIAS_MAY: /* Store to MAYBE the same location. */
237 if (store->op2 != val) /* Conflict if the value is different. */
238 goto doemit;
239 break; /* Otherwise continue searching. */
240 case ALIAS_MUST: /* Store to the same location. */
241 if (store->op2 == val) /* Same value: drop the new store. */
242 return DROPFOLD;
243 /* Different value: try to eliminate the redundant store. */
244 if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */
245 IRIns *ir;
246 /* Check for any intervening guards (includes conflicting loads). */
247 for (ir = IR(J->cur.nins-1); ir > store; ir--)
248 if (irt_isguard(ir->t))
249 goto doemit; /* No elimination possible. */
250 /* Remove redundant store from chain and replace with NOP. */
251 *refp = store->prev;
252 store->o = IR_NOP; /* Unchained NOP -- does anybody care? */
253 store->t.irt = IRT_NIL;
254 store->op1 = store->op2 = 0;
255 store->prev = 0;
256 /* Now emit the new store instead. */
257 }
258 goto doemit;
259 }
260 ref = *(refp = &store->prev);
261 }
262doemit:
263 return EMITFOLD; /* Otherwise we have a conflict or simply no match. */
264}
265
266/* -- ULOAD forwarding ---------------------------------------------------- */
267
268/* The current alias analysis for upvalues is very simplistic. It only
269** disambiguates between the unique upvalues of the same function.
270** This is good enough for now, since most upvalues are read-only.
271**
272** A more precise analysis would be feasible with the help of the parser:
273** generate a unique key for every upvalue, even across all prototypes.
274** Lacking a realistic use-case, it's unclear whether this is beneficial.
275*/
276static AliasRet aa_uref(IRIns *refa, IRIns *refb)
277{
278 if (refa->o != refb->o)
279 return ALIAS_NO; /* Different UREFx type. */
280 if (refa->op1 != refb->op1)
281 return ALIAS_MAY; /* Different function. */
282 else if (refa->op2 == refb->op2)
283 return ALIAS_MUST; /* Same function, same upvalue idx. */
284 else
285 return ALIAS_NO; /* Same function, different upvalue idx. */
286}
287
288/* ULOAD forwarding. */
289TRef LJ_FASTCALL lj_opt_fwd_uload(jit_State *J)
290{
291 IRRef uref = fins->op1;
292 IRRef lim = uref; /* Search limit. */
293 IRIns *xr = IR(uref);
294 IRRef ref;
295
296 /* Search for conflicting stores. */
297 ref = J->chain[IR_USTORE];
298 while (ref > uref) {
299 IRIns *store = IR(ref);
300 switch (aa_uref(xr, IR(store->op1))) {
301 case ALIAS_NO: break; /* Continue searching. */
302 case ALIAS_MAY: lim = ref; goto conflict; /* Limit search for load. */
303 case ALIAS_MUST: return store->op2; /* Store forwarding. */
304 }
305 ref = store->prev;
306 }
307
308conflict:
309 /* Try to find a matching load. Below the conflicting store, if any. */
310 ref = J->chain[IR_ULOAD];
311 while (ref > lim) {
312 IRIns *load = IR(ref);
313 if (load->op1 == uref)
314 return ref; /* Load forwarding. */
315 ref = load->prev;
316 }
317 return EMITFOLD; /* Conflict or no match. */
318}
319
320/* USTORE elimination. */
321TRef LJ_FASTCALL lj_opt_dse_ustore(jit_State *J)
322{
323 IRRef xref = fins->op1; /* xREF reference. */
324 IRRef val = fins->op2; /* Stored value reference. */
325 IRIns *xr = IR(xref);
326 IRRef1 *refp = &J->chain[IR_USTORE];
327 IRRef ref = *refp;
328 while (ref > xref) { /* Search for redundant or conflicting stores. */
329 IRIns *store = IR(ref);
330 switch (aa_uref(xr, IR(store->op1))) {
331 case ALIAS_NO:
332 break; /* Continue searching. */
333 case ALIAS_MAY: /* Store to MAYBE the same location. */
334 if (store->op2 != val) /* Conflict if the value is different. */
335 goto doemit;
336 break; /* Otherwise continue searching. */
337 case ALIAS_MUST: /* Store to the same location. */
338 if (store->op2 == val) /* Same value: drop the new store. */
339 return DROPFOLD;
340 /* Different value: try to eliminate the redundant store. */
341 if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */
342 IRIns *ir;
343 /* Check for any intervening guards (includes conflicting loads). */
344 for (ir = IR(J->cur.nins-1); ir > store; ir--)
345 if (irt_isguard(ir->t))
346 goto doemit; /* No elimination possible. */
347 /* Remove redundant store from chain and replace with NOP. */
348 *refp = store->prev;
349 store->o = IR_NOP; /* Unchained NOP -- does anybody care? */
350 store->t.irt = IRT_NIL;
351 store->op1 = store->op2 = 0;
352 store->prev = 0;
353 /* Now emit the new store instead. */
354 }
355 goto doemit;
356 }
357 ref = *(refp = &store->prev);
358 }
359doemit:
360 return EMITFOLD; /* Otherwise we have a conflict or simply no match. */
361}
362
363/* -- FLOAD forwarding and FSTORE elimination ----------------------------- */
364
365/* Alias analysis for field access.
366** Field loads are cheap and field stores are rare.
367** Simple disambiguation based on field types is good enough.
368*/
369static AliasRet aa_fref(IRIns *refa, IRIns *refb)
370{
371 if (refa->op2 != refb->op2)
372 return ALIAS_NO; /* Different fields. */
373 if (refa->op1 == refb->op1)
374 return ALIAS_MUST; /* Same field, same object. */
375 else
376 return ALIAS_MAY; /* Same field, possibly different object. */
377}
378
379/* Only the loads for mutable fields end up here (see FOLD). */
380TRef LJ_FASTCALL lj_opt_fwd_fload(jit_State *J)
381{
382 IRRef oref = fins->op1; /* Object reference. */
383 IRRef fid = fins->op2; /* Field ID. */
384 IRRef lim = oref; /* Search limit. */
385 IRRef ref;
386
387 /* Search for conflicting stores. */
388 ref = J->chain[IR_FSTORE];
389 while (ref > oref) {
390 IRIns *store = IR(ref);
391 switch (aa_fref(fins, IR(store->op1))) {
392 case ALIAS_NO: break; /* Continue searching. */
393 case ALIAS_MAY: lim = ref; goto conflict; /* Limit search for load. */
394 case ALIAS_MUST: return store->op2; /* Store forwarding. */
395 }
396 ref = store->prev;
397 }
398
399 /* No conflicting store: const-fold field loads from allocations. */
400 if (fid == IRFL_TAB_META) {
401 IRIns *ir = IR(oref);
402 if (ir->o == IR_TNEW || ir->o == IR_TDUP)
403 return lj_ir_knull(J, IRT_TAB);
404 }
405
406conflict:
407 /* Try to find a matching load. Below the conflicting store, if any. */
408 ref = J->chain[IR_FLOAD];
409 while (ref > lim) {
410 IRIns *load = IR(ref);
411 if (load->op1 == oref && load->op2 == fid)
412 return ref; /* Load forwarding. */
413 ref = load->prev;
414 }
415 return EMITFOLD; /* Otherwise we have a conflict or simply no match. */
416}
417
418/* FSTORE elimination. */
419TRef LJ_FASTCALL lj_opt_dse_fstore(jit_State *J)
420{
421 IRRef fref = fins->op1; /* FREF reference. */
422 IRRef val = fins->op2; /* Stored value reference. */
423 IRIns *xr = IR(fref);
424 IRRef1 *refp = &J->chain[IR_FSTORE];
425 IRRef ref = *refp;
426 while (ref > fref) { /* Search for redundant or conflicting stores. */
427 IRIns *store = IR(ref);
428 switch (aa_fref(xr, IR(store->op1))) {
429 case ALIAS_NO:
430 break; /* Continue searching. */
431 case ALIAS_MAY:
432 if (store->op2 != val) /* Conflict if the value is different. */
433 goto doemit;
434 break; /* Otherwise continue searching. */
435 case ALIAS_MUST:
436 if (store->op2 == val) /* Same value: drop the new store. */
437 return DROPFOLD;
438 /* Different value: try to eliminate the redundant store. */
439 if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */
440 IRIns *ir;
441 /* Check for any intervening guards or conflicting loads. */
442 for (ir = IR(J->cur.nins-1); ir > store; ir--)
443 if (irt_isguard(ir->t) || (ir->o == IR_FLOAD && ir->op2 == xr->op2))
444 goto doemit; /* No elimination possible. */
445 /* Remove redundant store from chain and replace with NOP. */
446 *refp = store->prev;
447 store->o = IR_NOP; /* Unchained NOP -- does anybody care? */
448 store->t.irt = IRT_NIL;
449 store->op1 = store->op2 = 0;
450 store->prev = 0;
451 /* Now emit the new store instead. */
452 }
453 goto doemit;
454 }
455 ref = *(refp = &store->prev);
456 }
457doemit:
458 return EMITFOLD; /* Otherwise we have a conflict or simply no match. */
459}
460
461/* -- TLEN forwarding ----------------------------------------------------- */
462
463/* This is rather simplistic right now, but better than nothing. */
464TRef LJ_FASTCALL lj_opt_fwd_tlen(jit_State *J)
465{
466 IRRef tab = fins->op1; /* Table reference. */
467 IRRef lim = tab; /* Search limit. */
468 IRRef ref;
469
470 /* Any ASTORE is a conflict and limits the search. */
471 if (J->chain[IR_ASTORE] > lim) lim = J->chain[IR_ASTORE];
472
473 /* Search for conflicting HSTORE with numeric key. */
474 ref = J->chain[IR_HSTORE];
475 while (ref > lim) {
476 IRIns *store = IR(ref);
477 IRIns *href = IR(store->op1);
478 IRIns *key = IR(href->op2);
479 if (irt_isnum(key->o == IR_KSLOT ? IR(key->op1)->t : key->t)) {
480 lim = ref; /* Conflicting store found, limits search for TLEN. */
481 break;
482 }
483 ref = store->prev;
484 }
485
486 /* Try to find a matching load. Below the conflicting store, if any. */
487 ref = J->chain[IR_TLEN];
488 while (ref > lim) {
489 IRIns *tlen = IR(ref);
490 if (tlen->op1 == tab)
491 return ref; /* Load forwarding. */
492 ref = tlen->prev;
493 }
494 return EMITFOLD; /* Otherwise we have a conflict or simply no match. */
495}
496
497/* -- ASTORE/HSTORE previous type analysis -------------------------------- */
498
499/* Check whether the previous value for a table store is non-nil.
500** This can be derived either from a previous store or from a previous
501** load (because all loads from tables perform a type check).
502**
503** The result of the analysis can be used to avoid the metatable check
504** and the guard against HREF returning niltv. Both of these are cheap,
505** so let's not spend too much effort on the analysis.
506**
507** A result of 1 is exact: previous value CANNOT be nil.
508** A result of 0 is inexact: previous value MAY be nil.
509*/
510int lj_opt_fwd_wasnonnil(jit_State *J, IROpT loadop, IRRef xref)
511{
512 /* First check stores. */
513 IRRef ref = J->chain[loadop+IRDELTA_L2S];
514 while (ref > xref) {
515 IRIns *store = IR(ref);
516 if (store->op1 == xref) { /* Same xREF. */
517 /* A nil store MAY alias, but a non-nil store MUST alias. */
518 return !irt_isnil(store->t);
519 } else if (irt_isnil(store->t)) { /* Must check any nil store. */
520 IRRef skref = IR(store->op1)->op2;
521 IRRef xkref = IR(xref)->op2;
522 /* Same key type MAY alias. */
523 if (irt_sametype(IR(skref)->t, IR(xkref)->t)) {
524 if (skref == xkref || !irref_isk(skref) || !irref_isk(xkref))
525 return 0; /* A nil store with same const key or var key MAY alias. */
526 /* Different const keys CANNOT alias. */
527 } /* Different key types CANNOT alias. */
528 } /* Other non-nil stores MAY alias. */
529 ref = store->prev;
530 }
531
532 /* Check loads since nothing could be derived from stores. */
533 ref = J->chain[loadop];
534 while (ref > xref) {
535 IRIns *load = IR(ref);
536 if (load->op1 == xref) { /* Same xREF. */
537 /* A nil load MAY alias, but a non-nil load MUST alias. */
538 return !irt_isnil(load->t);
539 } /* Other non-nil loads MAY alias. */
540 ref = load->prev;
541 }
542 return 0; /* Nothing derived at all, previous value MAY be nil. */
543}
544
545/* ------------------------------------------------------------------------ */
546
547#undef IR
548#undef fins
549
550#endif