1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine, DFG - Data Flow Graph |
4 +----------------------------------------------------------------------+
5 | Copyright (c) The PHP Group |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | https://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
15 | Authors: Dmitry Stogov <dmitry@php.net> |
16 +----------------------------------------------------------------------+
17 */
18
19 #include "zend_compile.h"
20 #include "zend_dfg.h"
21
_zend_dfg_add_use_def_op(const zend_op_array * op_array,const zend_op * opline,uint32_t build_flags,zend_bitset use,zend_bitset def)22 static zend_always_inline void _zend_dfg_add_use_def_op(const zend_op_array *op_array, const zend_op *opline, uint32_t build_flags, zend_bitset use, zend_bitset def) /* {{{ */
23 {
24 uint32_t var_num;
25 const zend_op *next;
26
27 if (opline->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
28 var_num = EX_VAR_TO_NUM(opline->op1.var);
29 if (!zend_bitset_in(def, var_num)) {
30 zend_bitset_incl(use, var_num);
31 }
32 }
33 if (((opline->op2_type & (IS_VAR|IS_TMP_VAR)) != 0
34 && opline->opcode != ZEND_FE_FETCH_R
35 && opline->opcode != ZEND_FE_FETCH_RW)
36 || (opline->op2_type == IS_CV)) {
37 var_num = EX_VAR_TO_NUM(opline->op2.var);
38 if (!zend_bitset_in(def, var_num)) {
39 zend_bitset_incl(use, var_num);
40 }
41 }
42 if ((build_flags & ZEND_SSA_USE_CV_RESULTS)
43 && opline->result_type == IS_CV
44 && opline->opcode != ZEND_RECV) {
45 var_num = EX_VAR_TO_NUM(opline->result.var);
46 if (!zend_bitset_in(def, var_num)) {
47 zend_bitset_incl(use, var_num);
48 }
49 }
50
51 switch (opline->opcode) {
52 case ZEND_ASSIGN:
53 if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op2_type == IS_CV) {
54 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
55 }
56 if (opline->op1_type == IS_CV) {
57 add_op1_def:
58 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op1.var));
59 }
60 break;
61 case ZEND_ASSIGN_REF:
62 if (opline->op2_type == IS_CV) {
63 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
64 }
65 if (opline->op1_type == IS_CV) {
66 goto add_op1_def;
67 }
68 break;
69 case ZEND_ASSIGN_DIM:
70 case ZEND_ASSIGN_OBJ:
71 next = opline + 1;
72 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
73 var_num = EX_VAR_TO_NUM(next->op1.var);
74 if (!zend_bitset_in(def, var_num)) {
75 zend_bitset_incl(use, var_num);
76 }
77 if (build_flags & ZEND_SSA_RC_INFERENCE && next->op1_type == IS_CV) {
78 zend_bitset_incl(def, var_num);
79 }
80 }
81 if (opline->op1_type == IS_CV) {
82 goto add_op1_def;
83 }
84 break;
85 case ZEND_ASSIGN_OBJ_REF:
86 next = opline + 1;
87 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
88 var_num = EX_VAR_TO_NUM(next->op1.var);
89 if (!zend_bitset_in(def, var_num)) {
90 zend_bitset_incl(use, var_num);
91 }
92 if (next->op1_type == IS_CV) {
93 zend_bitset_incl(def, var_num);
94 }
95 }
96 if (opline->op1_type == IS_CV) {
97 goto add_op1_def;
98 }
99 break;
100 case ZEND_ASSIGN_STATIC_PROP:
101 next = opline + 1;
102 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
103 var_num = EX_VAR_TO_NUM(next->op1.var);
104 if (!zend_bitset_in(def, var_num)) {
105 zend_bitset_incl(use, var_num);
106 }
107 if ((build_flags & ZEND_SSA_RC_INFERENCE) && next->op1_type == IS_CV) {
108 zend_bitset_incl(def, var_num);
109 }
110 }
111 break;
112 case ZEND_ASSIGN_STATIC_PROP_REF:
113 next = opline + 1;
114 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
115 var_num = EX_VAR_TO_NUM(next->op1.var);
116 if (!zend_bitset_in(def, var_num)) {
117 zend_bitset_incl(use, var_num);
118 }
119 if (next->op1_type == IS_CV) {
120 zend_bitset_incl(def, var_num);
121 }
122 }
123 break;
124 case ZEND_ASSIGN_STATIC_PROP_OP:
125 case ZEND_FRAMELESS_ICALL_3:
126 next = opline + 1;
127 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
128 var_num = EX_VAR_TO_NUM(next->op1.var);
129 if (!zend_bitset_in(def, var_num)) {
130 zend_bitset_incl(use, var_num);
131 }
132 }
133 break;
134 case ZEND_ASSIGN_DIM_OP:
135 case ZEND_ASSIGN_OBJ_OP:
136 next = opline + 1;
137 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
138 var_num = EX_VAR_TO_NUM(next->op1.var);
139 if (!zend_bitset_in(def, var_num)) {
140 zend_bitset_incl(use, var_num);
141 }
142 }
143 if (opline->op1_type == IS_CV) {
144 goto add_op1_def;
145 }
146 break;
147 case ZEND_ASSIGN_OP:
148 case ZEND_PRE_INC:
149 case ZEND_PRE_DEC:
150 case ZEND_POST_INC:
151 case ZEND_POST_DEC:
152 case ZEND_BIND_GLOBAL:
153 case ZEND_BIND_STATIC:
154 case ZEND_BIND_INIT_STATIC_OR_JMP:
155 case ZEND_SEND_VAR_NO_REF:
156 case ZEND_SEND_VAR_NO_REF_EX:
157 case ZEND_SEND_VAR_EX:
158 case ZEND_SEND_FUNC_ARG:
159 case ZEND_SEND_REF:
160 case ZEND_SEND_UNPACK:
161 case ZEND_FE_RESET_RW:
162 case ZEND_MAKE_REF:
163 case ZEND_PRE_INC_OBJ:
164 case ZEND_PRE_DEC_OBJ:
165 case ZEND_POST_INC_OBJ:
166 case ZEND_POST_DEC_OBJ:
167 case ZEND_UNSET_DIM:
168 case ZEND_UNSET_OBJ:
169 case ZEND_FETCH_DIM_W:
170 case ZEND_FETCH_DIM_RW:
171 case ZEND_FETCH_DIM_FUNC_ARG:
172 case ZEND_FETCH_DIM_UNSET:
173 case ZEND_FETCH_LIST_W:
174 if (opline->op1_type == IS_CV) {
175 goto add_op1_def;
176 }
177 break;
178 case ZEND_SEND_VAR:
179 case ZEND_CAST:
180 case ZEND_QM_ASSIGN:
181 case ZEND_JMP_SET:
182 case ZEND_COALESCE:
183 case ZEND_FE_RESET_R:
184 if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op1_type == IS_CV) {
185 goto add_op1_def;
186 }
187 break;
188 case ZEND_ADD_ARRAY_UNPACK:
189 var_num = EX_VAR_TO_NUM(opline->result.var);
190 if (!zend_bitset_in(def, var_num)) {
191 zend_bitset_incl(use, var_num);
192 }
193 break;
194 case ZEND_ADD_ARRAY_ELEMENT:
195 var_num = EX_VAR_TO_NUM(opline->result.var);
196 if (!zend_bitset_in(def, var_num)) {
197 zend_bitset_incl(use, var_num);
198 }
199 ZEND_FALLTHROUGH;
200 case ZEND_INIT_ARRAY:
201 if (((build_flags & ZEND_SSA_RC_INFERENCE)
202 || (opline->extended_value & ZEND_ARRAY_ELEMENT_REF))
203 && opline->op1_type == IS_CV) {
204 goto add_op1_def;
205 }
206 break;
207 case ZEND_YIELD:
208 if (opline->op1_type == IS_CV
209 && ((op_array->fn_flags & ZEND_ACC_RETURN_REFERENCE)
210 || (build_flags & ZEND_SSA_RC_INFERENCE))) {
211 goto add_op1_def;
212 }
213 break;
214 case ZEND_UNSET_CV:
215 goto add_op1_def;
216 case ZEND_VERIFY_RETURN_TYPE:
217 if (opline->op1_type & (IS_TMP_VAR|IS_VAR|IS_CV)) {
218 goto add_op1_def;
219 }
220 break;
221 case ZEND_FE_FETCH_R:
222 case ZEND_FE_FETCH_RW:
223 #if 0
224 /* This special case was handled above the switch */
225 if (opline->op2_type != IS_CV) {
226 op2_use = -1; /* not used */
227 }
228 #endif
229 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
230 break;
231 case ZEND_BIND_LEXICAL:
232 if ((opline->extended_value & ZEND_BIND_REF) || (build_flags & ZEND_SSA_RC_INFERENCE)) {
233 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
234 }
235 break;
236 default:
237 break;
238 }
239
240 if (opline->result_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
241 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->result.var));
242 }
243 }
244 /* }}} */
245
zend_dfg_add_use_def_op(const zend_op_array * op_array,const zend_op * opline,uint32_t build_flags,zend_bitset use,zend_bitset def)246 ZEND_API void zend_dfg_add_use_def_op(const zend_op_array *op_array, const zend_op *opline, uint32_t build_flags, zend_bitset use, zend_bitset def) /* {{{ */
247 {
248 _zend_dfg_add_use_def_op(op_array, opline, build_flags, use, def);
249 }
250 /* }}} */
251
zend_build_dfg(const zend_op_array * op_array,const zend_cfg * cfg,zend_dfg * dfg,uint32_t build_flags)252 void zend_build_dfg(const zend_op_array *op_array, const zend_cfg *cfg, zend_dfg *dfg, uint32_t build_flags) /* {{{ */
253 {
254 int set_size;
255 zend_basic_block *blocks = cfg->blocks;
256 int blocks_count = cfg->blocks_count;
257 zend_bitset tmp, def, use, in, out;
258 int k;
259 int j;
260
261 set_size = dfg->size;
262 tmp = dfg->tmp;
263 def = dfg->def;
264 use = dfg->use;
265 in = dfg->in;
266 out = dfg->out;
267
268 /* Collect "def" and "use" sets */
269 for (j = 0; j < blocks_count; j++) {
270 zend_op *opline, *end;
271 zend_bitset b_use, b_def;
272
273 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
274 continue;
275 }
276
277 opline = op_array->opcodes + blocks[j].start;
278 end = opline + blocks[j].len;
279 b_use = DFG_BITSET(use, set_size, j);
280 b_def = DFG_BITSET(def, set_size, j);
281 for (; opline < end; opline++) {
282 if (opline->opcode != ZEND_OP_DATA) {
283 _zend_dfg_add_use_def_op(op_array, opline, build_flags, b_use, b_def);
284 }
285 }
286 }
287
288 /* Calculate "in" and "out" sets */
289 {
290 uint32_t worklist_len = zend_bitset_len(blocks_count);
291 zend_bitset worklist;
292 ALLOCA_FLAG(use_heap);
293 worklist = ZEND_BITSET_ALLOCA(worklist_len, use_heap);
294 memset(worklist, 0, worklist_len * ZEND_BITSET_ELM_SIZE);
295 for (j = 0; j < blocks_count; j++) {
296 zend_bitset_incl(worklist, j);
297 }
298 while (!zend_bitset_empty(worklist, worklist_len)) {
299 /* We use the last block on the worklist, because predecessors tend to be located
300 * before the succeeding block, so this converges faster. */
301 j = zend_bitset_last(worklist, worklist_len);
302 zend_bitset_excl(worklist, j);
303
304 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
305 continue;
306 }
307 if (blocks[j].successors_count != 0) {
308 zend_bitset_copy(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[0]), set_size);
309 for (k = 1; k < blocks[j].successors_count; k++) {
310 zend_bitset_union(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[k]), set_size);
311 }
312 } else {
313 zend_bitset_clear(DFG_BITSET(out, set_size, j), set_size);
314 }
315 zend_bitset_union_with_difference(tmp, DFG_BITSET(use, set_size, j), DFG_BITSET(out, set_size, j), DFG_BITSET(def, set_size, j), set_size);
316 if (!zend_bitset_equal(DFG_BITSET(in, set_size, j), tmp, set_size)) {
317 zend_bitset_copy(DFG_BITSET(in, set_size, j), tmp, set_size);
318
319 /* Add predecessors of changed block to worklist */
320 {
321 int *predecessors = &cfg->predecessors[blocks[j].predecessor_offset];
322 for (k = 0; k < blocks[j].predecessors_count; k++) {
323 zend_bitset_incl(worklist, predecessors[k]);
324 }
325 }
326 }
327 }
328
329 free_alloca(worklist, use_heap);
330 }
331 }
332 /* }}} */
333
