diff options
Diffstat (limited to 'src/lj_opt_sink.c')
-rw-r--r-- | src/lj_opt_sink.c | 244 |
1 files changed, 244 insertions, 0 deletions
diff --git a/src/lj_opt_sink.c b/src/lj_opt_sink.c new file mode 100644 index 00000000..80ab5b6e --- /dev/null +++ b/src/lj_opt_sink.c | |||
@@ -0,0 +1,244 @@ | |||
1 | /* | ||
2 | ** SINK: Allocation Sinking and Store Sinking. | ||
3 | ** Copyright (C) 2005-2012 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 | if (ir + 255 < irs) | ||
36 | return NULL; /* Out of range. */ | ||
37 | return ir; /* Return allocation. */ | ||
38 | } | ||
39 | |||
40 | /* Recursively check whether a value depends on a PHI. */ | ||
41 | static int sink_phidep(jit_State *J, IRRef ref) | ||
42 | { | ||
43 | IRIns *ir = IR(ref); | ||
44 | if (irt_isphi(ir->t)) return 1; | ||
45 | if (ir->op1 >= REF_FIRST && sink_phidep(J, ir->op1)) return 1; | ||
46 | if (ir->op2 >= REF_FIRST && sink_phidep(J, ir->op2)) return 1; | ||
47 | return 0; | ||
48 | } | ||
49 | |||
50 | /* Check whether a value is a sinkable PHI or a non-PHI. */ | ||
51 | static int sink_checkphi(jit_State *J, IRIns *ira, IRRef ref) | ||
52 | { | ||
53 | if (ref >= REF_FIRST) { | ||
54 | IRIns *ir = IR(ref); | ||
55 | if (irt_isphi(ir->t) || (ir->o == IR_CONV && ir->op2 == IRCONV_NUM_INT && | ||
56 | irt_isphi(IR(ir->op1)->t))) { | ||
57 | ira->prev++; | ||
58 | return 1; /* Sinkable PHI. */ | ||
59 | } | ||
60 | return !sink_phidep(J, ref); /* Must be a non-PHI then. */ | ||
61 | } | ||
62 | return 1; /* Constant (non-PHI). */ | ||
63 | } | ||
64 | |||
65 | /* Mark non-sinkable allocations using single-pass backward propagation. | ||
66 | ** | ||
67 | ** Roots for the marking process are: | ||
68 | ** - Some PHIs or snapshots (see below). | ||
69 | ** - Non-PHI, non-constant values stored to PHI allocations. | ||
70 | ** - All guards. | ||
71 | ** - Any remaining loads not eliminated by store-to-load forwarding. | ||
72 | ** - Stores with non-constant keys. | ||
73 | ** - All stored values. | ||
74 | */ | ||
75 | static void sink_mark_ins(jit_State *J) | ||
76 | { | ||
77 | IRIns *ir, *irlast = IR(J->cur.nins-1); | ||
78 | for (ir = irlast ; ; ir--) { | ||
79 | switch (ir->o) { | ||
80 | case IR_BASE: | ||
81 | return; /* Finished. */ | ||
82 | case IR_CALLL: /* IRCALL_lj_tab_len */ | ||
83 | case IR_ALOAD: case IR_HLOAD: case IR_XLOAD: | ||
84 | irt_setmark(IR(ir->op1)->t); /* Mark ref for remaining loads. */ | ||
85 | break; | ||
86 | case IR_FLOAD: | ||
87 | if (irt_ismarked(ir->t) || ir->op2 == IRFL_TAB_META) | ||
88 | irt_setmark(IR(ir->op1)->t); /* Mark table for remaining loads. */ | ||
89 | break; | ||
90 | case IR_ASTORE: case IR_HSTORE: case IR_FSTORE: case IR_XSTORE: { | ||
91 | IRIns *ira = sink_checkalloc(J, ir); | ||
92 | if (!ira || (irt_isphi(ira->t) && !sink_checkphi(J, ira, ir->op2))) | ||
93 | irt_setmark(IR(ir->op1)->t); /* Mark ineligible ref. */ | ||
94 | irt_setmark(IR(ir->op2)->t); /* Mark stored value. */ | ||
95 | break; | ||
96 | } | ||
97 | #if LJ_HASFFI | ||
98 | case IR_CNEWI: | ||
99 | if (irt_isphi(ir->t) && | ||
100 | (!sink_checkphi(J, ir, ir->op2) || | ||
101 | (LJ_32 && ir+1 < irlast && (ir+1)->o == IR_HIOP && | ||
102 | !sink_checkphi(J, ir, (ir+1)->op2)))) | ||
103 | irt_setmark(ir->t); /* Mark ineligible allocation. */ | ||
104 | /* fallthrough */ | ||
105 | #endif | ||
106 | case IR_USTORE: | ||
107 | irt_setmark(IR(ir->op2)->t); /* Mark stored value. */ | ||
108 | break; | ||
109 | #if LJ_HASFFI | ||
110 | case IR_CALLXS: | ||
111 | #endif | ||
112 | case IR_CALLS: | ||
113 | irt_setmark(IR(ir->op1)->t); /* Mark (potentially) stored values. */ | ||
114 | break; | ||
115 | case IR_PHI: { | ||
116 | IRIns *irl = IR(ir->op1), *irr = IR(ir->op2); | ||
117 | irl->prev = irr->prev = 0; /* Clear PHI value counts. */ | ||
118 | if (irl->o == irr->o && | ||
119 | (irl->o == IR_TNEW || irl->o == IR_TDUP || | ||
120 | (LJ_HASFFI && (irl->o == IR_CNEW || irl->o == IR_CNEWI)))) | ||
121 | break; | ||
122 | irt_setmark(irl->t); | ||
123 | irt_setmark(irr->t); | ||
124 | break; | ||
125 | } | ||
126 | default: | ||
127 | if (irt_ismarked(ir->t) || irt_isguard(ir->t)) { /* Propagate mark. */ | ||
128 | if (ir->op1 >= REF_FIRST) irt_setmark(IR(ir->op1)->t); | ||
129 | if (ir->op2 >= REF_FIRST) irt_setmark(IR(ir->op2)->t); | ||
130 | } | ||
131 | break; | ||
132 | } | ||
133 | } | ||
134 | } | ||
135 | |||
136 | /* Mark all instructions referenced by a snapshot. */ | ||
137 | static void sink_mark_snap(jit_State *J, SnapShot *snap) | ||
138 | { | ||
139 | SnapEntry *map = &J->cur.snapmap[snap->mapofs]; | ||
140 | MSize n, nent = snap->nent; | ||
141 | for (n = 0; n < nent; n++) { | ||
142 | IRRef ref = snap_ref(map[n]); | ||
143 | if (!irref_isk(ref)) | ||
144 | irt_setmark(IR(ref)->t); | ||
145 | } | ||
146 | } | ||
147 | |||
148 | /* Iteratively remark PHI refs with differing marks or PHI value counts. */ | ||
149 | static void sink_remark_phi(jit_State *J) | ||
150 | { | ||
151 | IRIns *ir; | ||
152 | int remark; | ||
153 | do { | ||
154 | remark = 0; | ||
155 | for (ir = IR(J->cur.nins-1); ir->o == IR_PHI; ir--) { | ||
156 | IRIns *irl = IR(ir->op1), *irr = IR(ir->op2); | ||
157 | if (((irl->t.irt ^ irr->t.irt) & IRT_MARK)) | ||
158 | remark = 1; | ||
159 | else if (irl->prev == irr->prev) | ||
160 | continue; | ||
161 | irt_setmark(IR(ir->op1)->t); | ||
162 | irt_setmark(IR(ir->op2)->t); | ||
163 | } | ||
164 | } while (remark); | ||
165 | } | ||
166 | |||
167 | /* Sweep instructions and mark sunken allocations and stores. */ | ||
168 | static void sink_sweep_ins(jit_State *J) | ||
169 | { | ||
170 | IRIns *ir, *irfirst = IR(J->cur.nk); | ||
171 | for (ir = IR(J->cur.nins-1) ; ir >= irfirst; ir--) { | ||
172 | switch (ir->o) { | ||
173 | case IR_ASTORE: case IR_HSTORE: case IR_FSTORE: case IR_XSTORE: { | ||
174 | IRIns *ira = sink_checkalloc(J, ir); | ||
175 | if (ira && !irt_ismarked(ira->t)) | ||
176 | ir->prev = REGSP(RID_SINK, (int)(ir - ira)); | ||
177 | else | ||
178 | ir->prev = REGSP_INIT; | ||
179 | break; | ||
180 | } | ||
181 | case IR_NEWREF: | ||
182 | if (!irt_ismarked(ir->t)) { | ||
183 | ir->prev = REGSP(RID_SINK, 0); | ||
184 | } else { | ||
185 | irt_clearmark(ir->t); | ||
186 | ir->prev = REGSP_INIT; | ||
187 | } | ||
188 | break; | ||
189 | #if LJ_HASFFI | ||
190 | case IR_CNEW: case IR_CNEWI: | ||
191 | #endif | ||
192 | case IR_TNEW: case IR_TDUP: | ||
193 | if (!irt_ismarked(ir->t)) { | ||
194 | ir->t.irt &= ~IRT_GUARD; | ||
195 | ir->prev = REGSP(RID_SINK, 0); | ||
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 | IR(REF_BASE)->prev = 1; /* Signal SINK flags to assembler. */ | ||
219 | } | ||
220 | |||
221 | /* Allocation sinking and store sinking. | ||
222 | ** | ||
223 | ** 1. Mark all non-sinkable allocations. | ||
224 | ** 2. Then sink all remaining allocations and the related stores. | ||
225 | */ | ||
226 | void lj_opt_sink(jit_State *J) | ||
227 | { | ||
228 | const uint32_t need = (JIT_F_OPT_SINK|JIT_F_OPT_FWD| | ||
229 | JIT_F_OPT_DCE|JIT_F_OPT_CSE|JIT_F_OPT_FOLD); | ||
230 | if ((J->flags & need) == need && | ||
231 | (J->chain[IR_TNEW] || J->chain[IR_TDUP] || | ||
232 | (LJ_HASFFI && (J->chain[IR_CNEW] || J->chain[IR_CNEWI])))) { | ||
233 | if (!J->loopref) | ||
234 | sink_mark_snap(J, &J->cur.snap[J->cur.nsnap-1]); | ||
235 | sink_mark_ins(J); | ||
236 | if (J->loopref) | ||
237 | sink_remark_phi(J); | ||
238 | sink_sweep_ins(J); | ||
239 | } | ||
240 | } | ||
241 | |||
242 | #undef IR | ||
243 | |||
244 | #endif | ||