diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/luajit-2.0/src/lj_opt_mem.c | 861 |
1 files changed, 0 insertions, 861 deletions
diff --git a/libraries/luajit-2.0/src/lj_opt_mem.c b/libraries/luajit-2.0/src/lj_opt_mem.c deleted file mode 100644 index a90d097..0000000 --- a/libraries/luajit-2.0/src/lj_opt_mem.c +++ /dev/null | |||
@@ -1,861 +0,0 @@ | |||
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-2011 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 fright (&J->fold.right) | ||
25 | |||
26 | /* | ||
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(). | ||
29 | */ | ||
30 | |||
31 | /* Return values from alias analysis. */ | ||
32 | typedef enum { | ||
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). */ | ||
36 | } AliasRet; | ||
37 | |||
38 | /* -- ALOAD/HLOAD forwarding and ASTORE/HSTORE elimination ---------------- */ | ||
39 | |||
40 | /* Simplified escape analysis: check for intervening stores. */ | ||
41 | static AliasRet aa_escape(jit_State *J, IRIns *ir, IRIns *stop) | ||
42 | { | ||
43 | IRRef ref = (IRRef)(ir - J->cur.ir); /* The ref that might be stored. */ | ||
44 | for (ir++; ir < stop; ir++) | ||
45 | if (ir->op2 == ref && | ||
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. */ | ||
50 | } | ||
51 | |||
52 | /* Alias analysis for two different table references. */ | ||
53 | static AliasRet aa_table(jit_State *J, IRRef ta, IRRef tb) | ||
54 | { | ||
55 | IRIns *taba = IR(ta), *tabb = IR(tb); | ||
56 | int newa, newb; | ||
57 | lua_assert(ta != 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); | ||
62 | if (newa && newb) | ||
63 | return ALIAS_NO; /* Two different allocations never alias. */ | ||
64 | if (newb) { /* At least one allocation? */ | ||
65 | IRIns *tmp = taba; taba = tabb; tabb = tmp; | ||
66 | } else if (!newa) { | ||
67 | return ALIAS_MAY; /* Anything else: we just don't know. */ | ||
68 | } | ||
69 | return aa_escape(J, taba, tabb); | ||
70 | } | ||
71 | |||
72 | /* Alias analysis for array and hash access using key-based disambiguation. */ | ||
73 | static AliasRet aa_ahref(jit_State *J, IRIns *refa, IRIns *refb) | ||
74 | { | ||
75 | IRRef ka = refa->op2; | ||
76 | IRRef kb = refb->op2; | ||
77 | IRIns *keya, *keyb; | ||
78 | IRRef ta, tb; | ||
79 | if (refa == refb) | ||
80 | return ALIAS_MUST; /* Shortcut for same refs. */ | ||
81 | keya = IR(ka); | ||
82 | if (keya->o == IR_KSLOT) { ka = keya->op1; keya = IR(ka); } | ||
83 | keyb = IR(kb); | ||
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; | ||
87 | if (ka == kb) { | ||
88 | /* Same key. Check for same table with different ref (NEWREF vs. HREF). */ | ||
89 | if (ta == tb) | ||
90 | return ALIAS_MUST; /* Same key, same table. */ | ||
91 | else | ||
92 | return aa_table(J, ta, tb); /* Same key, possibly different table. */ | ||
93 | } | ||
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)) { | ||
103 | basea = keya->op1; | ||
104 | ofsa = IR(keya->op2)->i; | ||
105 | if (basea == kb && ofsa != 0) | ||
106 | return ALIAS_NO; /* t[base+-ofs] vs. t[base]. */ | ||
107 | } | ||
108 | if (keyb->o == IR_ADD && irref_isk(keyb->op2)) { | ||
109 | baseb = keyb->op1; | ||
110 | ofsb = IR(keyb->op2)->i; | ||
111 | if (ka == baseb && ofsb != 0) | ||
112 | return ALIAS_NO; /* t[base] vs. t[base+-ofs]. */ | ||
113 | } | ||
114 | if (basea == baseb && ofsa != ofsb) | ||
115 | return ALIAS_NO; /* t[base+-o1] vs. t[base+-o2] and o1 != o2. */ | ||
116 | } else { | ||
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. */ | ||
122 | } | ||
123 | if (ta == tb) | ||
124 | return ALIAS_MAY; /* Same table, cannot disambiguate keys. */ | ||
125 | else | ||
126 | return aa_table(J, ta, tb); /* Try to disambiguate tables. */ | ||
127 | } | ||
128 | |||
129 | /* Array and hash load forwarding. */ | ||
130 | static TRef fwd_ahload(jit_State *J, IRRef xref) | ||
131 | { | ||
132 | IRIns *xr = IR(xref); | ||
133 | IRRef lim = xref; /* Search limit. */ | ||
134 | IRRef ref; | ||
135 | |||
136 | /* Search for conflicting stores. */ | ||
137 | ref = J->chain[fins->o+IRDELTA_L2S]; | ||
138 | while (ref > xref) { | ||
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. */ | ||
144 | } | ||
145 | ref = store->prev; | ||
146 | } | ||
147 | |||
148 | /* No conflicting store (yet): const-fold loads from allocations. */ | ||
149 | { | ||
150 | IRIns *ir = (xr->o == IR_HREFK || xr->o == IR_AREF) ? IR(xr->op1) : xr; | ||
151 | IRRef tab = ir->op1; | ||
152 | ir = IR(tab); | ||
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. | ||
157 | */ | ||
158 | if (xr->o == IR_AREF) { | ||
159 | IRRef ref2 = J->chain[IR_NEWREF]; | ||
160 | while (ref2 > tab) { | ||
161 | IRIns *newref = IR(ref2); | ||
162 | if (irt_isnum(IR(newref->op2)->t)) | ||
163 | goto cselim; | ||
164 | ref2 = newref->prev; | ||
165 | } | ||
166 | } | ||
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. | ||
171 | */ | ||
172 | while (ref > tab) { | ||
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. */ | ||
178 | } | ||
179 | ref = store->prev; | ||
180 | } | ||
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)) { | ||
185 | TValue keyv; | ||
186 | cTValue *tv; | ||
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); | ||
194 | else | ||
195 | return lj_ir_kstr(J, strV(tv)); | ||
196 | } | ||
197 | /* Othwerwise: don't intern as a constant. */ | ||
198 | } | ||
199 | } | ||
200 | |||
201 | cselim: | ||
202 | /* Try to find a matching load. Below the conflicting store, if any. */ | ||
203 | ref = J->chain[fins->o]; | ||
204 | while (ref > lim) { | ||
205 | IRIns *load = IR(ref); | ||
206 | if (load->op1 == xref) | ||
207 | return ref; /* Load forwarding. */ | ||
208 | ref = load->prev; | ||
209 | } | ||
210 | return 0; /* Conflict or no match. */ | ||
211 | } | ||
212 | |||
213 | /* Reassociate ALOAD across PHIs to handle t[i-1] forwarding case. */ | ||
214 | static TRef fwd_aload_reassoc(jit_State *J) | ||
215 | { | ||
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; | ||
225 | while (ref > lim) { | ||
226 | IRIns *ir = IR(ref); | ||
227 | if (ir->op1 == irx->op1 && ir->op2 == add2->op1) | ||
228 | return fwd_ahload(J, ref); | ||
229 | ref = ir->prev; | ||
230 | } | ||
231 | } | ||
232 | } | ||
233 | return 0; | ||
234 | } | ||
235 | |||
236 | /* ALOAD forwarding. */ | ||
237 | TRef LJ_FASTCALL lj_opt_fwd_aload(jit_State *J) | ||
238 | { | ||
239 | IRRef ref; | ||
240 | if ((ref = fwd_ahload(J, fins->op1)) || | ||
241 | (ref = fwd_aload_reassoc(J))) | ||
242 | return ref; | ||
243 | return EMITFOLD; | ||
244 | } | ||
245 | |||
246 | /* HLOAD forwarding. */ | ||
247 | TRef LJ_FASTCALL lj_opt_fwd_hload(jit_State *J) | ||
248 | { | ||
249 | IRRef ref = fwd_ahload(J, fins->op1); | ||
250 | if (ref) | ||
251 | return ref; | ||
252 | return EMITFOLD; | ||
253 | } | ||
254 | |||
255 | /* Check whether HREF of TNEW/TDUP can be folded to niltv. */ | ||
256 | int LJ_FASTCALL lj_opt_fwd_href_nokey(jit_State *J) | ||
257 | { | ||
258 | IRRef lim = fins->op1; /* Search limit. */ | ||
259 | IRRef ref; | ||
260 | |||
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]; | ||
264 | while (ref > lim) { | ||
265 | if (ref < J->chain[IR_NEWREF]) | ||
266 | return 0; /* Conflict. */ | ||
267 | ref = IR(ref)->prev; | ||
268 | } | ||
269 | } | ||
270 | |||
271 | /* Search for conflicting stores. */ | ||
272 | ref = J->chain[IR_HSTORE]; | ||
273 | while (ref > lim) { | ||
274 | IRIns *store = IR(ref); | ||
275 | if (aa_ahref(J, fins, IR(store->op1)) != ALIAS_NO) | ||
276 | return 0; /* Conflict. */ | ||
277 | ref = store->prev; | ||
278 | } | ||
279 | |||
280 | return 1; /* No conflict. Can fold to niltv. */ | ||
281 | } | ||
282 | |||
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) | ||
285 | { | ||
286 | IRRef ta = fins->op1; | ||
287 | IRRef ref = J->chain[IR_NEWREF]; | ||
288 | while (ref > lim) { | ||
289 | IRIns *newref = IR(ref); | ||
290 | if (ta == newref->op1 || aa_table(J, ta, newref->op1) != ALIAS_NO) | ||
291 | return 0; /* Conflict. */ | ||
292 | ref = newref->prev; | ||
293 | } | ||
294 | return 1; /* No conflict. Can safely FOLD/CSE. */ | ||
295 | } | ||
296 | |||
297 | /* ASTORE/HSTORE elimination. */ | ||
298 | TRef LJ_FASTCALL lj_opt_dse_ahstore(jit_State *J) | ||
299 | { | ||
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]; | ||
304 | IRRef ref = *refp; | ||
305 | while (ref > xref) { /* Search for redundant or conflicting stores. */ | ||
306 | IRIns *store = IR(ref); | ||
307 | switch (aa_ahref(J, xr, IR(store->op1))) { | ||
308 | case ALIAS_NO: | ||
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. */ | ||
312 | goto doemit; | ||
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. */ | ||
316 | return DROPFOLD; | ||
317 | /* Different value: try to eliminate the redundant store. */ | ||
318 | if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */ | ||
319 | IRIns *ir; | ||
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. */ | ||
325 | *refp = store->prev; | ||
326 | store->o = IR_NOP; | ||
327 | store->t.irt = IRT_NIL; | ||
328 | store->op1 = store->op2 = 0; | ||
329 | store->prev = 0; | ||
330 | /* Now emit the new store instead. */ | ||
331 | } | ||
332 | goto doemit; | ||
333 | } | ||
334 | ref = *(refp = &store->prev); | ||
335 | } | ||
336 | doemit: | ||
337 | return EMITFOLD; /* Otherwise we have a conflict or simply no match. */ | ||
338 | } | ||
339 | |||
340 | /* -- ULOAD forwarding ---------------------------------------------------- */ | ||
341 | |||
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. | ||
345 | ** | ||
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. | ||
349 | */ | ||
350 | static AliasRet aa_uref(IRIns *refa, IRIns *refb) | ||
351 | { | ||
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. */ | ||
357 | else | ||
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. */ | ||
362 | else | ||
363 | return ALIAS_MAY; /* No conclusion can be drawn for same hash value. */ | ||
364 | } | ||
365 | } | ||
366 | |||
367 | /* ULOAD forwarding. */ | ||
368 | TRef LJ_FASTCALL lj_opt_fwd_uload(jit_State *J) | ||
369 | { | ||
370 | IRRef uref = fins->op1; | ||
371 | IRRef lim = uref; /* Search limit. */ | ||
372 | IRIns *xr = IR(uref); | ||
373 | IRRef ref; | ||
374 | |||
375 | /* Search for conflicting stores. */ | ||
376 | ref = J->chain[IR_USTORE]; | ||
377 | while (ref > uref) { | ||
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. */ | ||
383 | } | ||
384 | ref = store->prev; | ||
385 | } | ||
386 | |||
387 | cselim: | ||
388 | /* Try to find a matching load. Below the conflicting store, if any. */ | ||
389 | return lj_opt_cselim(J, lim); | ||
390 | } | ||
391 | |||
392 | /* USTORE elimination. */ | ||
393 | TRef LJ_FASTCALL lj_opt_dse_ustore(jit_State *J) | ||
394 | { | ||
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]; | ||
399 | IRRef ref = *refp; | ||
400 | while (ref > xref) { /* Search for redundant or conflicting stores. */ | ||
401 | IRIns *store = IR(ref); | ||
402 | switch (aa_uref(xr, IR(store->op1))) { | ||
403 | case ALIAS_NO: | ||
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. */ | ||
407 | goto doemit; | ||
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. */ | ||
411 | return DROPFOLD; | ||
412 | /* Different value: try to eliminate the redundant store. */ | ||
413 | if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */ | ||
414 | IRIns *ir; | ||
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. */ | ||
420 | *refp = store->prev; | ||
421 | store->o = IR_NOP; | ||
422 | store->t.irt = IRT_NIL; | ||
423 | store->op1 = store->op2 = 0; | ||
424 | store->prev = 0; | ||
425 | /* Now emit the new store instead. */ | ||
426 | } | ||
427 | goto doemit; | ||
428 | } | ||
429 | ref = *(refp = &store->prev); | ||
430 | } | ||
431 | doemit: | ||
432 | return EMITFOLD; /* Otherwise we have a conflict or simply no match. */ | ||
433 | } | ||
434 | |||
435 | /* -- FLOAD forwarding and FSTORE elimination ----------------------------- */ | ||
436 | |||
437 | /* Alias analysis for field access. | ||
438 | ** Field loads are cheap and field stores are rare. | ||
439 | ** Simple disambiguation based on field types is good enough. | ||
440 | */ | ||
441 | static AliasRet aa_fref(jit_State *J, IRIns *refa, IRIns *refb) | ||
442 | { | ||
443 | if (refa->op2 != refb->op2) | ||
444 | return ALIAS_NO; /* Different fields. */ | ||
445 | if (refa->op1 == refb->op1) | ||
446 | return ALIAS_MUST; /* Same field, same object. */ | ||
447 | else if (refa->op2 >= IRFL_TAB_META && refa->op2 <= IRFL_TAB_NOMM) | ||
448 | return aa_table(J, refa->op1, refb->op1); /* Disambiguate tables. */ | ||
449 | else | ||
450 | return ALIAS_MAY; /* Same field, possibly different object. */ | ||
451 | } | ||
452 | |||
453 | /* Only the loads for mutable fields end up here (see FOLD). */ | ||
454 | TRef LJ_FASTCALL lj_opt_fwd_fload(jit_State *J) | ||
455 | { | ||
456 | IRRef oref = fins->op1; /* Object reference. */ | ||
457 | IRRef fid = fins->op2; /* Field ID. */ | ||
458 | IRRef lim = oref; /* Search limit. */ | ||
459 | IRRef ref; | ||
460 | |||
461 | /* Search for conflicting stores. */ | ||
462 | ref = J->chain[IR_FSTORE]; | ||
463 | while (ref > oref) { | ||
464 | IRIns *store = IR(ref); | ||
465 | switch (aa_fref(J, fins, IR(store->op1))) { | ||
466 | case ALIAS_NO: break; /* Continue searching. */ | ||
467 | case ALIAS_MAY: lim = ref; goto cselim; /* Limit search for load. */ | ||
468 | case ALIAS_MUST: return store->op2; /* Store forwarding. */ | ||
469 | } | ||
470 | ref = store->prev; | ||
471 | } | ||
472 | |||
473 | /* No conflicting store: const-fold field loads from allocations. */ | ||
474 | if (fid == IRFL_TAB_META) { | ||
475 | IRIns *ir = IR(oref); | ||
476 | if (ir->o == IR_TNEW || ir->o == IR_TDUP) | ||
477 | return lj_ir_knull(J, IRT_TAB); | ||
478 | } | ||
479 | |||
480 | cselim: | ||
481 | /* Try to find a matching load. Below the conflicting store, if any. */ | ||
482 | return lj_opt_cselim(J, lim); | ||
483 | } | ||
484 | |||
485 | /* FSTORE elimination. */ | ||
486 | TRef LJ_FASTCALL lj_opt_dse_fstore(jit_State *J) | ||
487 | { | ||
488 | IRRef fref = fins->op1; /* FREF reference. */ | ||
489 | IRRef val = fins->op2; /* Stored value reference. */ | ||
490 | IRIns *xr = IR(fref); | ||
491 | IRRef1 *refp = &J->chain[IR_FSTORE]; | ||
492 | IRRef ref = *refp; | ||
493 | while (ref > fref) { /* Search for redundant or conflicting stores. */ | ||
494 | IRIns *store = IR(ref); | ||
495 | switch (aa_fref(J, xr, IR(store->op1))) { | ||
496 | case ALIAS_NO: | ||
497 | break; /* Continue searching. */ | ||
498 | case ALIAS_MAY: | ||
499 | if (store->op2 != val) /* Conflict if the value is different. */ | ||
500 | goto doemit; | ||
501 | break; /* Otherwise continue searching. */ | ||
502 | case ALIAS_MUST: | ||
503 | if (store->op2 == val) /* Same value: drop the new store. */ | ||
504 | return DROPFOLD; | ||
505 | /* Different value: try to eliminate the redundant store. */ | ||
506 | if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */ | ||
507 | IRIns *ir; | ||
508 | /* Check for any intervening guards or conflicting loads. */ | ||
509 | for (ir = IR(J->cur.nins-1); ir > store; ir--) | ||
510 | if (irt_isguard(ir->t) || (ir->o == IR_FLOAD && ir->op2 == xr->op2)) | ||
511 | goto doemit; /* No elimination possible. */ | ||
512 | /* Remove redundant store from chain and replace with NOP. */ | ||
513 | *refp = store->prev; | ||
514 | store->o = IR_NOP; | ||
515 | store->t.irt = IRT_NIL; | ||
516 | store->op1 = store->op2 = 0; | ||
517 | store->prev = 0; | ||
518 | /* Now emit the new store instead. */ | ||
519 | } | ||
520 | goto doemit; | ||
521 | } | ||
522 | ref = *(refp = &store->prev); | ||
523 | } | ||
524 | doemit: | ||
525 | return EMITFOLD; /* Otherwise we have a conflict or simply no match. */ | ||
526 | } | ||
527 | |||
528 | /* -- XLOAD forwarding and XSTORE elimination ----------------------------- */ | ||
529 | |||
530 | /* Find cdata allocation for a reference (if any). */ | ||
531 | static IRIns *aa_findcnew(jit_State *J, IRIns *ir) | ||
532 | { | ||
533 | while (ir->o == IR_ADD) { | ||
534 | if (!irref_isk(ir->op1)) { | ||
535 | IRIns *ir1 = aa_findcnew(J, IR(ir->op1)); /* Left-recursion. */ | ||
536 | if (ir1) return ir1; | ||
537 | } | ||
538 | if (irref_isk(ir->op2)) return NULL; | ||
539 | ir = IR(ir->op2); /* Flatten right-recursion. */ | ||
540 | } | ||
541 | return ir->o == IR_CNEW ? ir : NULL; | ||
542 | } | ||
543 | |||
544 | /* Alias analysis for two cdata allocations. */ | ||
545 | static AliasRet aa_cnew(jit_State *J, IRIns *refa, IRIns *refb) | ||
546 | { | ||
547 | IRIns *cnewa = aa_findcnew(J, refa); | ||
548 | IRIns *cnewb = aa_findcnew(J, refb); | ||
549 | if (cnewa == cnewb) | ||
550 | return ALIAS_MAY; /* Same allocation or neither is an allocation. */ | ||
551 | if (cnewa && cnewb) | ||
552 | return ALIAS_NO; /* Two different allocations never alias. */ | ||
553 | if (cnewb) { cnewa = cnewb; refb = refa; } | ||
554 | return aa_escape(J, cnewa, refb); | ||
555 | } | ||
556 | |||
557 | /* Alias analysis for XLOAD/XSTORE. */ | ||
558 | static AliasRet aa_xref(jit_State *J, IRIns *refa, IRIns *xa, IRIns *xb) | ||
559 | { | ||
560 | ptrdiff_t ofsa = 0, ofsb = 0; | ||
561 | IRIns *refb = IR(xb->op1); | ||
562 | IRIns *basea = refa, *baseb = refb; | ||
563 | /* This implements (very) strict aliasing rules. | ||
564 | ** Different types do NOT alias, except for differences in signedness. | ||
565 | ** NYI: this also prevents type punning through unions. | ||
566 | */ | ||
567 | if (irt_sametype(xa->t, xb->t)) { | ||
568 | if (refa == refb) | ||
569 | return ALIAS_MUST; /* Shortcut for same refs with identical type. */ | ||
570 | } else if (!(irt_typerange(xa->t, IRT_I8, IRT_U64) && | ||
571 | ((xa->t.irt - IRT_I8) ^ (xb->t.irt - IRT_I8)) == 1)) { | ||
572 | return ALIAS_NO; | ||
573 | } | ||
574 | /* Offset-based disambiguation. */ | ||
575 | if (refa->o == IR_ADD && irref_isk(refa->op2)) { | ||
576 | IRIns *irk = IR(refa->op2); | ||
577 | basea = IR(refa->op1); | ||
578 | ofsa = (LJ_64 && irk->o == IR_KINT64) ? (ptrdiff_t)ir_k64(irk)->u64 : | ||
579 | (ptrdiff_t)irk->i; | ||
580 | if (basea == refb && ofsa != 0) | ||
581 | return ALIAS_NO; /* base+-ofs vs. base. */ | ||
582 | } | ||
583 | if (refb->o == IR_ADD && irref_isk(refb->op2)) { | ||
584 | IRIns *irk = IR(refb->op2); | ||
585 | baseb = IR(refb->op1); | ||
586 | ofsb = (LJ_64 && irk->o == IR_KINT64) ? (ptrdiff_t)ir_k64(irk)->u64 : | ||
587 | (ptrdiff_t)irk->i; | ||
588 | if (refa == baseb && ofsb != 0) | ||
589 | return ALIAS_NO; /* base vs. base+-ofs. */ | ||
590 | } | ||
591 | if (basea == baseb) { | ||
592 | /* This assumes strictly-typed, non-overlapping accesses. */ | ||
593 | if (ofsa != ofsb) | ||
594 | return ALIAS_NO; /* base+-o1 vs. base+-o2 and o1 != o2. */ | ||
595 | return ALIAS_MUST; /* Unsigned vs. signed access to the same address. */ | ||
596 | } | ||
597 | /* NYI: structural disambiguation. */ | ||
598 | return aa_cnew(J, basea, baseb); /* Try to disambiguate allocations. */ | ||
599 | } | ||
600 | |||
601 | /* Return CSEd reference or 0. Caveat: swaps lower ref to the right! */ | ||
602 | static IRRef reassoc_trycse(jit_State *J, IROp op, IRRef op1, IRRef op2) | ||
603 | { | ||
604 | IRRef ref = J->chain[op]; | ||
605 | IRRef lim = op1; | ||
606 | if (op2 > lim) { lim = op2; op2 = op1; op1 = lim; } | ||
607 | while (ref > lim) { | ||
608 | IRIns *ir = IR(ref); | ||
609 | if (ir->op1 == op1 && ir->op2 == op2) | ||
610 | return ref; | ||
611 | ref = ir->prev; | ||
612 | } | ||
613 | return 0; | ||
614 | } | ||
615 | |||
616 | /* Reassociate index references. */ | ||
617 | static IRRef reassoc_xref(jit_State *J, IRIns *ir) | ||
618 | { | ||
619 | ptrdiff_t ofs = 0; | ||
620 | if (ir->o == IR_ADD && irref_isk(ir->op2)) { /* Get constant offset. */ | ||
621 | IRIns *irk = IR(ir->op2); | ||
622 | ofs = (LJ_64 && irk->o == IR_KINT64) ? (ptrdiff_t)ir_k64(irk)->u64 : | ||
623 | (ptrdiff_t)irk->i; | ||
624 | ir = IR(ir->op1); | ||
625 | } | ||
626 | if (ir->o == IR_ADD) { /* Add of base + index. */ | ||
627 | /* Index ref > base ref for loop-carried dependences. Only check op1. */ | ||
628 | IRIns *ir2, *ir1 = IR(ir->op1); | ||
629 | int32_t shift = 0; | ||
630 | IRRef idxref; | ||
631 | /* Determine index shifts. Don't bother with IR_MUL here. */ | ||
632 | if (ir1->o == IR_BSHL && irref_isk(ir1->op2)) | ||
633 | shift = IR(ir1->op2)->i; | ||
634 | else if (ir1->o == IR_ADD && ir1->op1 == ir1->op2) | ||
635 | shift = 1; | ||
636 | else | ||
637 | ir1 = ir; | ||
638 | ir2 = IR(ir1->op1); | ||
639 | /* A non-reassociated add. Must be a loop-carried dependence. */ | ||
640 | if (ir2->o == IR_ADD && irt_isint(ir2->t) && irref_isk(ir2->op2)) | ||
641 | ofs += (ptrdiff_t)IR(ir2->op2)->i << shift; | ||
642 | else | ||
643 | return 0; | ||
644 | idxref = ir2->op1; | ||
645 | /* Try to CSE the reassociated chain. Give up if not found. */ | ||
646 | if (ir1 != ir && | ||
647 | !(idxref = reassoc_trycse(J, ir1->o, idxref, | ||
648 | ir1->o == IR_BSHL ? ir1->op2 : idxref))) | ||
649 | return 0; | ||
650 | if (!(idxref = reassoc_trycse(J, IR_ADD, idxref, ir->op2))) | ||
651 | return 0; | ||
652 | if (ofs != 0) { | ||
653 | IRRef refk = tref_ref(lj_ir_kintp(J, ofs)); | ||
654 | if (!(idxref = reassoc_trycse(J, IR_ADD, idxref, refk))) | ||
655 | return 0; | ||
656 | } | ||
657 | return idxref; /* Success, found a reassociated index reference. Phew. */ | ||
658 | } | ||
659 | return 0; /* Failure. */ | ||
660 | } | ||
661 | |||
662 | /* XLOAD forwarding. */ | ||
663 | TRef LJ_FASTCALL lj_opt_fwd_xload(jit_State *J) | ||
664 | { | ||
665 | IRRef xref = fins->op1; | ||
666 | IRIns *xr = IR(xref); | ||
667 | IRRef lim = xref; /* Search limit. */ | ||
668 | IRRef ref; | ||
669 | |||
670 | if ((fins->op2 & IRXLOAD_READONLY)) | ||
671 | goto cselim; | ||
672 | if ((fins->op2 & IRXLOAD_VOLATILE)) | ||
673 | goto doemit; | ||
674 | |||
675 | /* Search for conflicting stores. */ | ||
676 | ref = J->chain[IR_XSTORE]; | ||
677 | retry: | ||
678 | if (J->chain[IR_CALLXS] > lim) lim = J->chain[IR_CALLXS]; | ||
679 | if (J->chain[IR_XBAR] > lim) lim = J->chain[IR_XBAR]; | ||
680 | while (ref > lim) { | ||
681 | IRIns *store = IR(ref); | ||
682 | switch (aa_xref(J, xr, fins, store)) { | ||
683 | case ALIAS_NO: break; /* Continue searching. */ | ||
684 | case ALIAS_MAY: lim = ref; goto cselim; /* Limit search for load. */ | ||
685 | case ALIAS_MUST: | ||
686 | /* Emit conversion if the loaded type doesn't match the forwarded type. */ | ||
687 | if (!irt_sametype(fins->t, IR(store->op2)->t)) { | ||
688 | IRType st = irt_type(fins->t); | ||
689 | if (st == IRT_I8 || st == IRT_I16) { /* Trunc + sign-extend. */ | ||
690 | st |= IRCONV_SEXT; | ||
691 | } else if (st == IRT_U8 || st == IRT_U16) { /* Trunc + zero-extend. */ | ||
692 | } else if (st == IRT_INT && !irt_isint(IR(store->op2)->t)) { | ||
693 | st = irt_type(IR(store->op2)->t); /* Needs dummy CONV.int.*. */ | ||
694 | } else { /* I64/U64 are boxed, U32 is hidden behind a CONV.num.u32. */ | ||
695 | goto store_fwd; | ||
696 | } | ||
697 | fins->ot = IRTI(IR_CONV); | ||
698 | fins->op1 = store->op2; | ||
699 | fins->op2 = (IRT_INT<<5)|st; | ||
700 | return RETRYFOLD; | ||
701 | } | ||
702 | store_fwd: | ||
703 | return store->op2; /* Store forwarding. */ | ||
704 | } | ||
705 | ref = store->prev; | ||
706 | } | ||
707 | |||
708 | cselim: | ||
709 | /* Try to find a matching load. Below the conflicting store, if any. */ | ||
710 | ref = J->chain[IR_XLOAD]; | ||
711 | while (ref > lim) { | ||
712 | /* CSE for XLOAD depends on the type, but not on the IRXLOAD_* flags. */ | ||
713 | if (IR(ref)->op1 == xref && irt_sametype(IR(ref)->t, fins->t)) | ||
714 | return ref; | ||
715 | ref = IR(ref)->prev; | ||
716 | } | ||
717 | |||
718 | /* Reassociate XLOAD across PHIs to handle a[i-1] forwarding case. */ | ||
719 | if (!(fins->op2 & IRXLOAD_READONLY) && J->chain[IR_LOOP] && | ||
720 | xref == fins->op1 && (xref = reassoc_xref(J, xr)) != 0) { | ||
721 | ref = J->chain[IR_XSTORE]; | ||
722 | while (ref > lim) /* Skip stores that have already been checked. */ | ||
723 | ref = IR(ref)->prev; | ||
724 | lim = xref; | ||
725 | xr = IR(xref); | ||
726 | goto retry; /* Retry with the reassociated reference. */ | ||
727 | } | ||
728 | doemit: | ||
729 | return EMITFOLD; | ||
730 | } | ||
731 | |||
732 | /* XSTORE elimination. */ | ||
733 | TRef LJ_FASTCALL lj_opt_dse_xstore(jit_State *J) | ||
734 | { | ||
735 | IRRef xref = fins->op1; | ||
736 | IRIns *xr = IR(xref); | ||
737 | IRRef lim = xref; /* Search limit. */ | ||
738 | IRRef val = fins->op2; /* Stored value reference. */ | ||
739 | IRRef1 *refp = &J->chain[IR_XSTORE]; | ||
740 | IRRef ref = *refp; | ||
741 | if (J->chain[IR_CALLXS] > lim) lim = J->chain[IR_CALLXS]; | ||
742 | if (J->chain[IR_XBAR] > lim) lim = J->chain[IR_XBAR]; | ||
743 | while (ref > lim) { /* Search for redundant or conflicting stores. */ | ||
744 | IRIns *store = IR(ref); | ||
745 | switch (aa_xref(J, xr, fins, store)) { | ||
746 | case ALIAS_NO: | ||
747 | break; /* Continue searching. */ | ||
748 | case ALIAS_MAY: | ||
749 | if (store->op2 != val) /* Conflict if the value is different. */ | ||
750 | goto doemit; | ||
751 | break; /* Otherwise continue searching. */ | ||
752 | case ALIAS_MUST: | ||
753 | if (store->op2 == val) /* Same value: drop the new store. */ | ||
754 | return DROPFOLD; | ||
755 | /* Different value: try to eliminate the redundant store. */ | ||
756 | if (ref > J->chain[IR_LOOP]) { /* Quick check to avoid crossing LOOP. */ | ||
757 | IRIns *ir; | ||
758 | /* Check for any intervening guards or any XLOADs (no AA performed). */ | ||
759 | for (ir = IR(J->cur.nins-1); ir > store; ir--) | ||
760 | if (irt_isguard(ir->t) || ir->o == IR_XLOAD) | ||
761 | goto doemit; /* No elimination possible. */ | ||
762 | /* Remove redundant store from chain and replace with NOP. */ | ||
763 | *refp = store->prev; | ||
764 | store->o = IR_NOP; | ||
765 | store->t.irt = IRT_NIL; | ||
766 | store->op1 = store->op2 = 0; | ||
767 | store->prev = 0; | ||
768 | /* Now emit the new store instead. */ | ||
769 | } | ||
770 | goto doemit; | ||
771 | } | ||
772 | ref = *(refp = &store->prev); | ||
773 | } | ||
774 | doemit: | ||
775 | return EMITFOLD; /* Otherwise we have a conflict or simply no match. */ | ||
776 | } | ||
777 | |||
778 | /* -- Forwarding of lj_tab_len -------------------------------------------- */ | ||
779 | |||
780 | /* This is rather simplistic right now, but better than nothing. */ | ||
781 | TRef LJ_FASTCALL lj_opt_fwd_tab_len(jit_State *J) | ||
782 | { | ||
783 | IRRef tab = fins->op1; /* Table reference. */ | ||
784 | IRRef lim = tab; /* Search limit. */ | ||
785 | IRRef ref; | ||
786 | |||
787 | /* Any ASTORE is a conflict and limits the search. */ | ||
788 | if (J->chain[IR_ASTORE] > lim) lim = J->chain[IR_ASTORE]; | ||
789 | |||
790 | /* Search for conflicting HSTORE with numeric key. */ | ||
791 | ref = J->chain[IR_HSTORE]; | ||
792 | while (ref > lim) { | ||
793 | IRIns *store = IR(ref); | ||
794 | IRIns *href = IR(store->op1); | ||
795 | IRIns *key = IR(href->op2); | ||
796 | if (irt_isnum(key->o == IR_KSLOT ? IR(key->op1)->t : key->t)) { | ||
797 | lim = ref; /* Conflicting store found, limits search for TLEN. */ | ||
798 | break; | ||
799 | } | ||
800 | ref = store->prev; | ||
801 | } | ||
802 | |||
803 | /* Try to find a matching load. Below the conflicting store, if any. */ | ||
804 | return lj_opt_cselim(J, lim); | ||
805 | } | ||
806 | |||
807 | /* -- ASTORE/HSTORE previous type analysis -------------------------------- */ | ||
808 | |||
809 | /* Check whether the previous value for a table store is non-nil. | ||
810 | ** This can be derived either from a previous store or from a previous | ||
811 | ** load (because all loads from tables perform a type check). | ||
812 | ** | ||
813 | ** The result of the analysis can be used to avoid the metatable check | ||
814 | ** and the guard against HREF returning niltv. Both of these are cheap, | ||
815 | ** so let's not spend too much effort on the analysis. | ||
816 | ** | ||
817 | ** A result of 1 is exact: previous value CANNOT be nil. | ||
818 | ** A result of 0 is inexact: previous value MAY be nil. | ||
819 | */ | ||
820 | int lj_opt_fwd_wasnonnil(jit_State *J, IROpT loadop, IRRef xref) | ||
821 | { | ||
822 | /* First check stores. */ | ||
823 | IRRef ref = J->chain[loadop+IRDELTA_L2S]; | ||
824 | while (ref > xref) { | ||
825 | IRIns *store = IR(ref); | ||
826 | if (store->op1 == xref) { /* Same xREF. */ | ||
827 | /* A nil store MAY alias, but a non-nil store MUST alias. */ | ||
828 | return !irt_isnil(store->t); | ||
829 | } else if (irt_isnil(store->t)) { /* Must check any nil store. */ | ||
830 | IRRef skref = IR(store->op1)->op2; | ||
831 | IRRef xkref = IR(xref)->op2; | ||
832 | /* Same key type MAY alias. Need ALOAD check due to multiple int types. */ | ||
833 | if (loadop == IR_ALOAD || irt_sametype(IR(skref)->t, IR(xkref)->t)) { | ||
834 | if (skref == xkref || !irref_isk(skref) || !irref_isk(xkref)) | ||
835 | return 0; /* A nil store with same const key or var key MAY alias. */ | ||
836 | /* Different const keys CANNOT alias. */ | ||
837 | } /* Different key types CANNOT alias. */ | ||
838 | } /* Other non-nil stores MAY alias. */ | ||
839 | ref = store->prev; | ||
840 | } | ||
841 | |||
842 | /* Check loads since nothing could be derived from stores. */ | ||
843 | ref = J->chain[loadop]; | ||
844 | while (ref > xref) { | ||
845 | IRIns *load = IR(ref); | ||
846 | if (load->op1 == xref) { /* Same xREF. */ | ||
847 | /* A nil load MAY alias, but a non-nil load MUST alias. */ | ||
848 | return !irt_isnil(load->t); | ||
849 | } /* Other non-nil loads MAY alias. */ | ||
850 | ref = load->prev; | ||
851 | } | ||
852 | return 0; /* Nothing derived at all, previous value MAY be nil. */ | ||
853 | } | ||
854 | |||
855 | /* ------------------------------------------------------------------------ */ | ||
856 | |||
857 | #undef IR | ||
858 | #undef fins | ||
859 | #undef fright | ||
860 | |||
861 | #endif | ||