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. */
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 return ir; /* Return allocation. */
36}
37
38/* Recursively check whether a value depends on a PHI. */
39static 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. */
49static 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*/
74static 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. */
135static 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. */
147static void sink_remark_phi(jit_State *J)
148{
149 IRIns *ir;
150 int remark;
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. */
165static 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*/
232void 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