xref: /PHP-8.2/Zend/Optimizer/zend_dfg.c (revision 57e4bd2b)
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 			next = opline + 1;
126 			if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
127 				var_num = EX_VAR_TO_NUM(next->op1.var);
128 				if (!zend_bitset_in(def, var_num)) {
129 					zend_bitset_incl(use, var_num);
130 				}
131 			}
132 			break;
133 		case ZEND_ASSIGN_DIM_OP:
134 		case ZEND_ASSIGN_OBJ_OP:
135 			next = opline + 1;
136 			if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
137 				var_num = EX_VAR_TO_NUM(next->op1.var);
138 				if (!zend_bitset_in(def, var_num)) {
139 					zend_bitset_incl(use, var_num);
140 				}
141 			}
142 			if (opline->op1_type == IS_CV) {
143 				goto add_op1_def;
144 			}
145 			break;
146 		case ZEND_ASSIGN_OP:
147 		case ZEND_PRE_INC:
148 		case ZEND_PRE_DEC:
149 		case ZEND_POST_INC:
150 		case ZEND_POST_DEC:
151 		case ZEND_BIND_GLOBAL:
152 		case ZEND_BIND_STATIC:
153 		case ZEND_SEND_VAR_NO_REF:
154 		case ZEND_SEND_VAR_NO_REF_EX:
155 		case ZEND_SEND_VAR_EX:
156 		case ZEND_SEND_FUNC_ARG:
157 		case ZEND_SEND_REF:
158 		case ZEND_SEND_UNPACK:
159 		case ZEND_FE_RESET_RW:
160 		case ZEND_MAKE_REF:
161 		case ZEND_PRE_INC_OBJ:
162 		case ZEND_PRE_DEC_OBJ:
163 		case ZEND_POST_INC_OBJ:
164 		case ZEND_POST_DEC_OBJ:
165 		case ZEND_UNSET_DIM:
166 		case ZEND_UNSET_OBJ:
167 		case ZEND_FETCH_DIM_W:
168 		case ZEND_FETCH_DIM_RW:
169 		case ZEND_FETCH_DIM_FUNC_ARG:
170 		case ZEND_FETCH_DIM_UNSET:
171 		case ZEND_FETCH_LIST_W:
172 			if (opline->op1_type == IS_CV) {
173 				goto add_op1_def;
174 			}
175 			break;
176 		case ZEND_SEND_VAR:
177 		case ZEND_CAST:
178 		case ZEND_QM_ASSIGN:
179 		case ZEND_JMP_SET:
180 		case ZEND_COALESCE:
181 		case ZEND_FE_RESET_R:
182 			if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op1_type == IS_CV) {
183 				goto add_op1_def;
184 			}
185 			break;
186 		case ZEND_ADD_ARRAY_UNPACK:
187 			var_num = EX_VAR_TO_NUM(opline->result.var);
188 			if (!zend_bitset_in(def, var_num)) {
189 				zend_bitset_incl(use, var_num);
190 			}
191 			break;
192 		case ZEND_ADD_ARRAY_ELEMENT:
193 			var_num = EX_VAR_TO_NUM(opline->result.var);
194 			if (!zend_bitset_in(def, var_num)) {
195 				zend_bitset_incl(use, var_num);
196 			}
197 			ZEND_FALLTHROUGH;
198 		case ZEND_INIT_ARRAY:
199 			if (((build_flags & ZEND_SSA_RC_INFERENCE)
200 						|| (opline->extended_value & ZEND_ARRAY_ELEMENT_REF))
201 					&& opline->op1_type == IS_CV) {
202 				goto add_op1_def;
203 			}
204 			break;
205 		case ZEND_YIELD:
206 			if (opline->op1_type == IS_CV
207 					&& ((op_array->fn_flags & ZEND_ACC_RETURN_REFERENCE)
208 						|| (build_flags & ZEND_SSA_RC_INFERENCE))) {
209 				goto add_op1_def;
210 			}
211 			break;
212 		case ZEND_UNSET_CV:
213 			goto add_op1_def;
214 		case ZEND_VERIFY_RETURN_TYPE:
215 			if (opline->op1_type & (IS_TMP_VAR|IS_VAR|IS_CV)) {
216 				goto add_op1_def;
217 			}
218 			break;
219 		case ZEND_FE_FETCH_R:
220 		case ZEND_FE_FETCH_RW:
221 #if 0
222 			/* This special case was handled above the switch */
223 			if (opline->op2_type != IS_CV) {
224 				op2_use = -1; /* not used */
225 			}
226 #endif
227 			zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
228 			break;
229 		case ZEND_BIND_LEXICAL:
230 			if ((opline->extended_value & ZEND_BIND_REF) || (build_flags & ZEND_SSA_RC_INFERENCE)) {
231 				zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var));
232 			}
233 			break;
234 		default:
235 			break;
236 	}
237 
238 	if (opline->result_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
239 		zend_bitset_incl(def, EX_VAR_TO_NUM(opline->result.var));
240 	}
241 }
242 /* }}} */
243 
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)244 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) /* {{{ */
245 {
246 	_zend_dfg_add_use_def_op(op_array, opline, build_flags, use, def);
247 }
248 /* }}} */
249 
zend_build_dfg(const zend_op_array * op_array,const zend_cfg * cfg,zend_dfg * dfg,uint32_t build_flags)250 void zend_build_dfg(const zend_op_array *op_array, const zend_cfg *cfg, zend_dfg *dfg, uint32_t build_flags) /* {{{ */
251 {
252 	int set_size;
253 	zend_basic_block *blocks = cfg->blocks;
254 	int blocks_count = cfg->blocks_count;
255 	zend_bitset tmp, def, use, in, out;
256 	int k;
257 	int j;
258 
259 	set_size = dfg->size;
260 	tmp = dfg->tmp;
261 	def = dfg->def;
262 	use = dfg->use;
263 	in  = dfg->in;
264 	out = dfg->out;
265 
266 	/* Collect "def" and "use" sets */
267 	for (j = 0; j < blocks_count; j++) {
268 		zend_op *opline, *end;
269 		zend_bitset b_use, b_def;
270 
271 		if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
272 			continue;
273 		}
274 
275 		opline = op_array->opcodes + blocks[j].start;
276 		end = opline + blocks[j].len;
277 		b_use = DFG_BITSET(use, set_size, j);
278 		b_def = DFG_BITSET(def, set_size, j);
279 		for (; opline < end; opline++) {
280 			if (opline->opcode != ZEND_OP_DATA) {
281 				_zend_dfg_add_use_def_op(op_array, opline, build_flags, b_use, b_def);
282 			}
283 		}
284 	}
285 
286 	/* Calculate "in" and "out" sets */
287 	{
288 		uint32_t worklist_len = zend_bitset_len(blocks_count);
289 		zend_bitset worklist;
290 		ALLOCA_FLAG(use_heap);
291 		worklist = ZEND_BITSET_ALLOCA(worklist_len, use_heap);
292 		memset(worklist, 0, worklist_len * ZEND_BITSET_ELM_SIZE);
293 		for (j = 0; j < blocks_count; j++) {
294 			zend_bitset_incl(worklist, j);
295 		}
296 		while (!zend_bitset_empty(worklist, worklist_len)) {
297 			/* We use the last block on the worklist, because predecessors tend to be located
298 			 * before the succeeding block, so this converges faster. */
299 			j = zend_bitset_last(worklist, worklist_len);
300 			zend_bitset_excl(worklist, j);
301 
302 			if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
303 				continue;
304 			}
305 			if (blocks[j].successors_count != 0) {
306 				zend_bitset_copy(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[0]), set_size);
307 				for (k = 1; k < blocks[j].successors_count; k++) {
308 					zend_bitset_union(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[k]), set_size);
309 				}
310 			} else {
311 				zend_bitset_clear(DFG_BITSET(out, set_size, j), set_size);
312 			}
313 			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);
314 			if (!zend_bitset_equal(DFG_BITSET(in, set_size, j), tmp, set_size)) {
315 				zend_bitset_copy(DFG_BITSET(in, set_size, j), tmp, set_size);
316 
317 				/* Add predecessors of changed block to worklist */
318 				{
319 					int *predecessors = &cfg->predecessors[blocks[j].predecessor_offset];
320 					for (k = 0; k < blocks[j].predecessors_count; k++) {
321 						zend_bitset_incl(worklist, predecessors[k]);
322 					}
323 				}
324 			}
325 		}
326 
327 		free_alloca(worklist, use_heap);
328 	}
329 }
330 /* }}} */
331