aboutsummaryrefslogtreecommitdiff
path: root/src/lj_opt_sink.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lj_opt_sink.c')
-rw-r--r--src/lj_opt_sink.c244
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. */
22static 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. */
41static 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. */
51static 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*/
75static 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. */
137static 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. */
149static 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. */
168static 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*/
226void 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