1 | /* |
2 | ** SINK: Allocation Sinking and Store Sinking. |
3 | ** Copyright (C) 2005-2021 Mike Pall. See Copyright Notice in luajit.h |
4 | */ |
5 | |
6 | #define lj_opt_sink_c |
7 | #define LUA_CORE |
8 | |
9 | #include "lj_obj.h" |
10 | |
11 | #if LJ_HASJIT |
12 | |
13 | #include "lj_ir.h" |
14 | #include "lj_jit.h" |
15 | #include "lj_iropt.h" |
16 | #include "lj_target.h" |
17 | |
18 | /* Some local macros to save typing. Undef'd at the end. */ |
19 | #define IR(ref) (&J->cur.ir[(ref)]) |
20 | |
21 | /* Check whether the store ref points to an eligible allocation. */ |
22 | static IRIns *sink_checkalloc(jit_State *J, IRIns *irs) |
23 | { |
24 | IRIns *ir = IR(irs->op1); |
25 | if (!irref_isk(ir->op2)) |
26 | return NULL; /* Non-constant key. */ |
27 | if (ir->o == IR_HREFK || ir->o == IR_AREF) |
28 | ir = IR(ir->op1); |
29 | else if (!(ir->o == IR_HREF || ir->o == IR_NEWREF || |
30 | ir->o == IR_FREF || ir->o == IR_ADD)) |
31 | return NULL; /* Unhandled reference type (for XSTORE). */ |
32 | ir = IR(ir->op1); |
33 | if (!(ir->o == IR_TNEW || ir->o == IR_TDUP || ir->o == IR_CNEW)) |
34 | return NULL; /* Not an allocation. */ |
35 | return ir; /* Return allocation. */ |
36 | } |
37 | |
38 | /* Recursively check whether a value depends on a PHI. */ |
39 | static int sink_phidep(jit_State *J, IRRef ref) |
40 | { |
41 | IRIns *ir = IR(ref); |
42 | if (irt_isphi(ir->t)) return 1; |
43 | if (ir->op1 >= REF_FIRST && sink_phidep(J, ir->op1)) return 1; |
44 | if (ir->op2 >= REF_FIRST && sink_phidep(J, ir->op2)) return 1; |
45 | return 0; |
46 | } |
47 | |
48 | /* Check whether a value is a sinkable PHI or loop-invariant. */ |
49 | static int sink_checkphi(jit_State *J, IRIns *ira, IRRef ref) |
50 | { |
51 | if (ref >= REF_FIRST) { |
52 | IRIns *ir = IR(ref); |
53 | if (irt_isphi(ir->t) || (ir->o == IR_CONV && ir->op2 == IRCONV_NUM_INT && |
54 | irt_isphi(IR(ir->op1)->t))) { |
55 | ira->prev++; |
56 | return 1; /* Sinkable PHI. */ |
57 | } |
58 | /* Otherwise the value must be loop-invariant. */ |
59 | return ref < J->loopref && !sink_phidep(J, ref); |
60 | } |
61 | return 1; /* Constant (non-PHI). */ |
62 | } |
63 | |
64 | /* Mark non-sinkable allocations using single-pass backward propagation. |
65 | ** |
66 | ** Roots for the marking process are: |
67 | ** - Some PHIs or snapshots (see below). |
68 | ** - Non-PHI, non-constant values stored to PHI allocations. |
69 | ** - All guards. |
70 | ** - Any remaining loads not eliminated by store-to-load forwarding. |
71 | ** - Stores with non-constant keys. |
72 | ** - All stored values. |
73 | */ |
74 | static void sink_mark_ins(jit_State *J) |
75 | { |
76 | IRIns *ir, *irlast = IR(J->cur.nins-1); |
77 | for (ir = irlast ; ; ir--) { |
78 | switch (ir->o) { |
79 | case IR_BASE: |
80 | return; /* Finished. */ |
81 | case IR_ALOAD: case IR_HLOAD: case IR_XLOAD: case IR_TBAR: case IR_ALEN: |
82 | irt_setmark(IR(ir->op1)->t); /* Mark ref for remaining loads. */ |
83 | break; |
84 | case IR_FLOAD: |
85 | if (irt_ismarked(ir->t) || ir->op2 == IRFL_TAB_META) |
86 | irt_setmark(IR(ir->op1)->t); /* Mark table for remaining loads. */ |
87 | break; |
88 | case IR_ASTORE: case IR_HSTORE: case IR_FSTORE: case IR_XSTORE: { |
89 | IRIns *ira = sink_checkalloc(J, ir); |
90 | if (!ira || (irt_isphi(ira->t) && !sink_checkphi(J, ira, ir->op2))) |
91 | irt_setmark(IR(ir->op1)->t); /* Mark ineligible ref. */ |
92 | irt_setmark(IR(ir->op2)->t); /* Mark stored value. */ |
93 | break; |
94 | } |
95 | #if LJ_HASFFI |
96 | case IR_CNEWI: |
97 | if (irt_isphi(ir->t) && |
98 | (!sink_checkphi(J, ir, ir->op2) || |
99 | (LJ_32 && ir+1 < irlast && (ir+1)->o == IR_HIOP && |
100 | !sink_checkphi(J, ir, (ir+1)->op2)))) |
101 | irt_setmark(ir->t); /* Mark ineligible allocation. */ |
102 | #endif |
103 | /* fallthrough */ |
104 | case IR_USTORE: |
105 | irt_setmark(IR(ir->op2)->t); /* Mark stored value. */ |
106 | break; |
107 | #if LJ_HASFFI |
108 | case IR_CALLXS: |
109 | #endif |
110 | case IR_CALLS: |
111 | irt_setmark(IR(ir->op1)->t); /* Mark (potentially) stored values. */ |
112 | break; |
113 | case IR_PHI: { |
114 | IRIns *irl = IR(ir->op1), *irr = IR(ir->op2); |
115 | irl->prev = irr->prev = 0; /* Clear PHI value counts. */ |
116 | if (irl->o == irr->o && |
117 | (irl->o == IR_TNEW || irl->o == IR_TDUP || |
118 | (LJ_HASFFI && (irl->o == IR_CNEW || irl->o == IR_CNEWI)))) |
119 | break; |
120 | irt_setmark(irl->t); |
121 | irt_setmark(irr->t); |
122 | break; |
123 | } |
124 | default: |
125 | if (irt_ismarked(ir->t) || irt_isguard(ir->t)) { /* Propagate mark. */ |
126 | if (ir->op1 >= REF_FIRST) irt_setmark(IR(ir->op1)->t); |
127 | if (ir->op2 >= REF_FIRST) irt_setmark(IR(ir->op2)->t); |
128 | } |
129 | break; |
130 | } |
131 | } |
132 | } |
133 | |
134 | /* Mark all instructions referenced by a snapshot. */ |
135 | static void sink_mark_snap(jit_State *J, SnapShot *snap) |
136 | { |
137 | SnapEntry *map = &J->cur.snapmap[snap->mapofs]; |
138 | MSize n, nent = snap->nent; |
139 | for (n = 0; n < nent; n++) { |
140 | IRRef ref = snap_ref(map[n]); |
141 | if (!irref_isk(ref)) |
142 | irt_setmark(IR(ref)->t); |
143 | } |
144 | } |
145 | |
146 | /* Iteratively remark PHI refs with differing marks or PHI value counts. */ |
147 | static void (jit_State *J) |
148 | { |
149 | IRIns *ir; |
150 | int ; |
151 | do { |
152 | remark = 0; |
153 | for (ir = IR(J->cur.nins-1); ir->o == IR_PHI; ir--) { |
154 | IRIns *irl = IR(ir->op1), *irr = IR(ir->op2); |
155 | if (!((irl->t.irt ^ irr->t.irt) & IRT_MARK) && irl->prev == irr->prev) |
156 | continue; |
157 | remark |= (~(irl->t.irt & irr->t.irt) & IRT_MARK); |
158 | irt_setmark(IR(ir->op1)->t); |
159 | irt_setmark(IR(ir->op2)->t); |
160 | } |
161 | } while (remark); |
162 | } |
163 | |
164 | /* Sweep instructions and tag sunken allocations and stores. */ |
165 | static void sink_sweep_ins(jit_State *J) |
166 | { |
167 | IRIns *ir, *irbase = IR(REF_BASE); |
168 | for (ir = IR(J->cur.nins-1) ; ir >= irbase; ir--) { |
169 | switch (ir->o) { |
170 | case IR_ASTORE: case IR_HSTORE: case IR_FSTORE: case IR_XSTORE: { |
171 | IRIns *ira = sink_checkalloc(J, ir); |
172 | if (ira && !irt_ismarked(ira->t)) { |
173 | int delta = (int)(ir - ira); |
174 | ir->prev = REGSP(RID_SINK, delta > 255 ? 255 : delta); |
175 | } else { |
176 | ir->prev = REGSP_INIT; |
177 | } |
178 | break; |
179 | } |
180 | case IR_NEWREF: |
181 | if (!irt_ismarked(IR(ir->op1)->t)) { |
182 | ir->prev = REGSP(RID_SINK, 0); |
183 | } else { |
184 | irt_clearmark(ir->t); |
185 | ir->prev = REGSP_INIT; |
186 | } |
187 | break; |
188 | #if LJ_HASFFI |
189 | case IR_CNEW: case IR_CNEWI: |
190 | #endif |
191 | case IR_TNEW: case IR_TDUP: |
192 | if (!irt_ismarked(ir->t)) { |
193 | ir->t.irt &= ~IRT_GUARD; |
194 | ir->prev = REGSP(RID_SINK, 0); |
195 | J->cur.sinktags = 1; /* Signal present SINK tags to assembler. */ |
196 | } else { |
197 | irt_clearmark(ir->t); |
198 | ir->prev = REGSP_INIT; |
199 | } |
200 | break; |
201 | case IR_PHI: { |
202 | IRIns *ira = IR(ir->op2); |
203 | if (!irt_ismarked(ira->t) && |
204 | (ira->o == IR_TNEW || ira->o == IR_TDUP || |
205 | (LJ_HASFFI && (ira->o == IR_CNEW || ira->o == IR_CNEWI)))) { |
206 | ir->prev = REGSP(RID_SINK, 0); |
207 | } else { |
208 | ir->prev = REGSP_INIT; |
209 | } |
210 | break; |
211 | } |
212 | default: |
213 | irt_clearmark(ir->t); |
214 | ir->prev = REGSP_INIT; |
215 | break; |
216 | } |
217 | } |
218 | for (ir = IR(J->cur.nk); ir < irbase; ir++) { |
219 | irt_clearmark(ir->t); |
220 | ir->prev = REGSP_INIT; |
221 | /* The false-positive of irt_is64() for ASMREF_L (REF_NIL) is OK here. */ |
222 | if (irt_is64(ir->t) && ir->o != IR_KNULL) |
223 | ir++; |
224 | } |
225 | } |
226 | |
227 | /* Allocation sinking and store sinking. |
228 | ** |
229 | ** 1. Mark all non-sinkable allocations. |
230 | ** 2. Then sink all remaining allocations and the related stores. |
231 | */ |
232 | void lj_opt_sink(jit_State *J) |
233 | { |
234 | const uint32_t need = (JIT_F_OPT_SINK|JIT_F_OPT_FWD| |
235 | JIT_F_OPT_DCE|JIT_F_OPT_CSE|JIT_F_OPT_FOLD); |
236 | if ((J->flags & need) == need && |
237 | (J->chain[IR_TNEW] || J->chain[IR_TDUP] || |
238 | (LJ_HASFFI && (J->chain[IR_CNEW] || J->chain[IR_CNEWI])))) { |
239 | if (!J->loopref) |
240 | sink_mark_snap(J, &J->cur.snap[J->cur.nsnap-1]); |
241 | sink_mark_ins(J); |
242 | if (J->loopref) |
243 | sink_remark_phi(J); |
244 | sink_sweep_ins(J); |
245 | } |
246 | } |
247 | |
248 | #undef IR |
249 | |
250 | #endif |
251 | |