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 | http://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 "php.h"
20 #include "zend_compile.h"
21 #include "zend_dfg.h"
22
_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 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) /* {{{ */
24 {
25 uint32_t var_num;
26 const zend_op *next;
27
28 if (opline->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
29 var_num = EX_VAR_TO_NUM(opline->op1.var);
30 if (!zend_bitset_in(def, var_num)) {
31 zend_bitset_incl(use, var_num);
32 }
33 }
34 if (((opline->op2_type & (IS_VAR|IS_TMP_VAR)) != 0
35 && opline->opcode != ZEND_FE_FETCH_R
36 && opline->opcode != ZEND_FE_FETCH_RW)
37 || (opline->op2_type == IS_CV)) {
38 var_num = EX_VAR_TO_NUM(opline->op2.var);
39 if (!zend_bitset_in(def, var_num)) {
40 zend_bitset_incl(use, var_num);
41 }
42 }
43 if ((build_flags & ZEND_SSA_USE_CV_RESULTS)
44 && opline->result_type == IS_CV
45 && opline->opcode != ZEND_RECV) {
46 var_num = EX_VAR_TO_NUM(opline->result.var);
47 if (!zend_bitset_in(def, var_num)) {
48 zend_bitset_incl(use, var_num);
49 }
50 }
51
52 switch (opline->opcode) {
53 case ZEND_ASSIGN:
54 if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op2_type == IS_CV) {
55 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
56 }
57 if (opline->op1_type == IS_CV) {
58 add_op1_def:
59 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op1.var));
60 }
61 break;
62 case ZEND_ASSIGN_REF:
63 if (opline->op2_type == IS_CV) {
64 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
65 }
66 if (opline->op1_type == IS_CV) {
67 goto add_op1_def;
68 }
69 break;
70 case ZEND_ASSIGN_DIM:
71 case ZEND_ASSIGN_OBJ:
72 next = opline + 1;
73 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
74 var_num = EX_VAR_TO_NUM(next->op1.var);
75 if (!zend_bitset_in(def, var_num)) {
76 zend_bitset_incl(use, var_num);
77 }
78 if (build_flags & ZEND_SSA_RC_INFERENCE && next->op1_type == IS_CV) {
79 zend_bitset_incl(def, var_num);
80 }
81 }
82 if (opline->op1_type == IS_CV) {
83 goto add_op1_def;
84 }
85 break;
86 case ZEND_ASSIGN_OBJ_REF:
87 next = opline + 1;
88 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
89 var_num = EX_VAR_TO_NUM(next->op1.var);
90 if (!zend_bitset_in(def, var_num)) {
91 zend_bitset_incl(use, var_num);
92 }
93 if (next->op1_type == IS_CV) {
94 zend_bitset_incl(def, var_num);
95 }
96 }
97 if (opline->op1_type == IS_CV) {
98 goto add_op1_def;
99 }
100 break;
101 case ZEND_ASSIGN_STATIC_PROP:
102 next = opline + 1;
103 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
104 var_num = EX_VAR_TO_NUM(next->op1.var);
105 if (!zend_bitset_in(def, var_num)) {
106 zend_bitset_incl(use, var_num);
107 }
108 if ((build_flags & ZEND_SSA_RC_INFERENCE) && next->op1_type == IS_CV) {
109 zend_bitset_incl(def, var_num);
110 }
111 }
112 break;
113 case ZEND_ASSIGN_STATIC_PROP_REF:
114 next = opline + 1;
115 if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
116 var_num = EX_VAR_TO_NUM(next->op1.var);
117 if (!zend_bitset_in(def, var_num)) {
118 zend_bitset_incl(use, var_num);
119 }
120 if (next->op1_type == IS_CV) {
121 zend_bitset_incl(def, var_num);
122 }
123 }
124 break;
125 case ZEND_ASSIGN_STATIC_PROP_OP:
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_SEND_VAR_NO_REF:
155 case ZEND_SEND_VAR_NO_REF_EX:
156 case ZEND_SEND_VAR_EX:
157 case ZEND_SEND_FUNC_ARG:
158 case ZEND_SEND_REF:
159 case ZEND_SEND_UNPACK:
160 case ZEND_FE_RESET_RW:
161 case ZEND_MAKE_REF:
162 case ZEND_PRE_INC_OBJ:
163 case ZEND_PRE_DEC_OBJ:
164 case ZEND_POST_INC_OBJ:
165 case ZEND_POST_DEC_OBJ:
166 case ZEND_UNSET_DIM:
167 case ZEND_UNSET_OBJ:
168 case ZEND_FETCH_DIM_W:
169 case ZEND_FETCH_DIM_RW:
170 case ZEND_FETCH_DIM_FUNC_ARG:
171 case ZEND_FETCH_DIM_UNSET:
172 case ZEND_FETCH_LIST_W:
173 if (opline->op1_type == IS_CV) {
174 goto add_op1_def;
175 }
176 break;
177 case ZEND_SEND_VAR:
178 case ZEND_CAST:
179 case ZEND_QM_ASSIGN:
180 case ZEND_JMP_SET:
181 case ZEND_COALESCE:
182 case ZEND_FE_RESET_R:
183 if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op1_type == IS_CV) {
184 goto add_op1_def;
185 }
186 break;
187 case ZEND_ADD_ARRAY_UNPACK:
188 var_num = EX_VAR_TO_NUM(opline->result.var);
189 if (!zend_bitset_in(def, var_num)) {
190 zend_bitset_incl(use, var_num);
191 }
192 break;
193 case ZEND_ADD_ARRAY_ELEMENT:
194 var_num = EX_VAR_TO_NUM(opline->result.var);
195 if (!zend_bitset_in(def, var_num)) {
196 zend_bitset_incl(use, var_num);
197 }
198 /* break missing intentionally */
199 case ZEND_INIT_ARRAY:
200 if (((build_flags & ZEND_SSA_RC_INFERENCE)
201 || (opline->extended_value & ZEND_ARRAY_ELEMENT_REF))
202 && opline->op1_type == IS_CV) {
203 goto add_op1_def;
204 }
205 break;
206 case ZEND_YIELD:
207 if (opline->op1_type == IS_CV
208 && ((op_array->fn_flags & ZEND_ACC_RETURN_REFERENCE)
209 || (build_flags & ZEND_SSA_RC_INFERENCE))) {
210 goto add_op1_def;
211 }
212 break;
213 case ZEND_UNSET_CV:
214 goto add_op1_def;
215 case ZEND_VERIFY_RETURN_TYPE:
216 if (opline->op1_type & (IS_TMP_VAR|IS_VAR|IS_CV)) {
217 goto add_op1_def;
218 }
219 break;
220 case ZEND_FE_FETCH_R:
221 case ZEND_FE_FETCH_RW:
222 #if 0
223 /* This special case was handled above the switch */
224 if (opline->op2_type != IS_CV) {
225 op2_use = -1; /* not used */
226 }
227 #endif
228 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
229 break;
230 case ZEND_BIND_LEXICAL:
231 if ((opline->extended_value & ZEND_BIND_REF) || (build_flags & ZEND_SSA_RC_INFERENCE)) {
232 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
233 }
234 break;
235 default:
236 break;
237 }
238
239 if (opline->result_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
240 zend_bitset_incl(def, EX_VAR_TO_NUM(opline->result.var));
241 }
242 }
243 /* }}} */
244
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)245 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) /* {{{ */
246 {
247 _zend_dfg_add_use_def_op(op_array, opline, build_flags, use, def);
248 }
249 /* }}} */
250
zend_build_dfg(const zend_op_array * op_array,const zend_cfg * cfg,zend_dfg * dfg,uint32_t build_flags)251 int zend_build_dfg(const zend_op_array *op_array, const zend_cfg *cfg, zend_dfg *dfg, uint32_t build_flags) /* {{{ */
252 {
253 int set_size;
254 zend_basic_block *blocks = cfg->blocks;
255 int blocks_count = cfg->blocks_count;
256 zend_bitset tmp, def, use, in, out;
257 int k;
258 int j;
259
260 set_size = dfg->size;
261 tmp = dfg->tmp;
262 def = dfg->def;
263 use = dfg->use;
264 in = dfg->in;
265 out = dfg->out;
266
267 /* Collect "def" and "use" sets */
268 for (j = 0; j < blocks_count; j++) {
269 zend_op *opline, *end;
270 zend_bitset b_use, b_def;
271
272 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
273 continue;
274 }
275
276 opline = op_array->opcodes + blocks[j].start;
277 end = opline + blocks[j].len;
278 b_use = DFG_BITSET(use, set_size, j);
279 b_def = DFG_BITSET(def, set_size, j);
280 for (; opline < end; opline++) {
281 if (opline->opcode != ZEND_OP_DATA) {
282 _zend_dfg_add_use_def_op(op_array, opline, build_flags, b_use, b_def);
283 }
284 }
285 }
286
287 /* Calculate "in" and "out" sets */
288 {
289 uint32_t worklist_len = zend_bitset_len(blocks_count);
290 zend_bitset worklist;
291 ALLOCA_FLAG(use_heap);
292 worklist = ZEND_BITSET_ALLOCA(worklist_len, use_heap);
293 memset(worklist, 0, worklist_len * ZEND_BITSET_ELM_SIZE);
294 for (j = 0; j < blocks_count; j++) {
295 zend_bitset_incl(worklist, j);
296 }
297 while (!zend_bitset_empty(worklist, worklist_len)) {
298 /* We use the last block on the worklist, because predecessors tend to be located
299 * before the succeeding block, so this converges faster. */
300 j = zend_bitset_last(worklist, worklist_len);
301 zend_bitset_excl(worklist, j);
302
303 if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
304 continue;
305 }
306 if (blocks[j].successors_count != 0) {
307 zend_bitset_copy(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[0]), set_size);
308 for (k = 1; k < blocks[j].successors_count; k++) {
309 zend_bitset_union(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[k]), set_size);
310 }
311 } else {
312 zend_bitset_clear(DFG_BITSET(out, set_size, j), set_size);
313 }
314 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);
315 if (!zend_bitset_equal(DFG_BITSET(in, set_size, j), tmp, set_size)) {
316 zend_bitset_copy(DFG_BITSET(in, set_size, j), tmp, set_size);
317
318 /* Add predecessors of changed block to worklist */
319 {
320 int *predecessors = &cfg->predecessors[blocks[j].predecessor_offset];
321 for (k = 0; k < blocks[j].predecessors_count; k++) {
322 zend_bitset_incl(worklist, predecessors[k]);
323 }
324 }
325 }
326 }
327
328 free_alloca(worklist, use_heap);
329 }
330
331 return SUCCESS;
332 }
333 /* }}} */
334
