/src/php-src/Zend/Optimizer/zend_dfg.c
Line | Count | Source (jump to first uncovered line) |
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 | | |
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 | 1.33M | { |
24 | 1.33M | uint32_t var_num; |
25 | 1.33M | const zend_op *next; |
26 | | |
27 | 1.33M | if (opline->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { |
28 | 799k | var_num = EX_VAR_TO_NUM(opline->op1.var); |
29 | 799k | if (!zend_bitset_in(def, var_num)) { |
30 | 243k | zend_bitset_incl(use, var_num); |
31 | 243k | } |
32 | 799k | } |
33 | 1.33M | if (((opline->op2_type & (IS_VAR|IS_TMP_VAR)) != 0 |
34 | 1.33M | && opline->opcode != ZEND_FE_FETCH_R |
35 | 1.33M | && opline->opcode != ZEND_FE_FETCH_RW) |
36 | 1.33M | || (opline->op2_type == IS_CV)) { |
37 | 274k | var_num = EX_VAR_TO_NUM(opline->op2.var); |
38 | 274k | if (!zend_bitset_in(def, var_num)) { |
39 | 169k | zend_bitset_incl(use, var_num); |
40 | 169k | } |
41 | 274k | } |
42 | 1.33M | if ((build_flags & ZEND_SSA_USE_CV_RESULTS) |
43 | 1.33M | && opline->result_type == IS_CV |
44 | 1.33M | && opline->opcode != ZEND_RECV) { |
45 | 0 | var_num = EX_VAR_TO_NUM(opline->result.var); |
46 | 0 | if (!zend_bitset_in(def, var_num)) { |
47 | 0 | zend_bitset_incl(use, var_num); |
48 | 0 | } |
49 | 0 | } |
50 | | |
51 | 1.33M | switch (opline->opcode) { |
52 | 57.6k | case ZEND_ASSIGN: |
53 | 57.6k | if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op2_type == IS_CV) { |
54 | 0 | zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var)); |
55 | 0 | } |
56 | 57.6k | if (opline->op1_type == IS_CV) { |
57 | 103k | add_op1_def: |
58 | 103k | zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op1.var)); |
59 | 103k | } |
60 | 104k | break; |
61 | 104k | case ZEND_ASSIGN_REF: |
62 | 2.01k | if (opline->op2_type == IS_CV) { |
63 | 957 | zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var)); |
64 | 957 | } |
65 | 2.01k | if (opline->op1_type == IS_CV) { |
66 | 1.53k | goto add_op1_def; |
67 | 1.53k | } |
68 | 476 | break; |
69 | 6.76k | case ZEND_ASSIGN_DIM: |
70 | 14.3k | case ZEND_ASSIGN_OBJ: |
71 | 14.3k | next = opline + 1; |
72 | 14.3k | if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { |
73 | 8.03k | var_num = EX_VAR_TO_NUM(next->op1.var); |
74 | 8.03k | if (!zend_bitset_in(def, var_num)) { |
75 | 1.14k | zend_bitset_incl(use, var_num); |
76 | 1.14k | } |
77 | 8.03k | if (build_flags & ZEND_SSA_RC_INFERENCE && next->op1_type == IS_CV) { |
78 | 0 | zend_bitset_incl(def, var_num); |
79 | 0 | } |
80 | 8.03k | } |
81 | 14.3k | if (opline->op1_type == IS_CV) { |
82 | 8.97k | goto add_op1_def; |
83 | 8.97k | } |
84 | 5.41k | break; |
85 | 5.41k | case ZEND_ASSIGN_OBJ_REF: |
86 | 303 | next = opline + 1; |
87 | 303 | if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { |
88 | 303 | var_num = EX_VAR_TO_NUM(next->op1.var); |
89 | 303 | if (!zend_bitset_in(def, var_num)) { |
90 | 46 | zend_bitset_incl(use, var_num); |
91 | 46 | } |
92 | 303 | if (next->op1_type == IS_CV) { |
93 | 215 | zend_bitset_incl(def, var_num); |
94 | 215 | } |
95 | 303 | } |
96 | 303 | if (opline->op1_type == IS_CV) { |
97 | 172 | goto add_op1_def; |
98 | 172 | } |
99 | 131 | break; |
100 | 1.01k | case ZEND_ASSIGN_STATIC_PROP: |
101 | 1.01k | next = opline + 1; |
102 | 1.01k | if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { |
103 | 663 | var_num = EX_VAR_TO_NUM(next->op1.var); |
104 | 663 | if (!zend_bitset_in(def, var_num)) { |
105 | 346 | zend_bitset_incl(use, var_num); |
106 | 346 | } |
107 | 663 | if ((build_flags & ZEND_SSA_RC_INFERENCE) && next->op1_type == IS_CV) { |
108 | 0 | zend_bitset_incl(def, var_num); |
109 | 0 | } |
110 | 663 | } |
111 | 1.01k | break; |
112 | 110 | case ZEND_ASSIGN_STATIC_PROP_REF: |
113 | 110 | next = opline + 1; |
114 | 110 | if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { |
115 | 110 | var_num = EX_VAR_TO_NUM(next->op1.var); |
116 | 110 | if (!zend_bitset_in(def, var_num)) { |
117 | 4 | zend_bitset_incl(use, var_num); |
118 | 4 | } |
119 | 110 | if (next->op1_type == IS_CV) { |
120 | 34 | zend_bitset_incl(def, var_num); |
121 | 34 | } |
122 | 110 | } |
123 | 110 | break; |
124 | 12 | case ZEND_ASSIGN_STATIC_PROP_OP: |
125 | 12 | case ZEND_FRAMELESS_ICALL_3: |
126 | 12 | next = opline + 1; |
127 | 12 | if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { |
128 | 12 | var_num = EX_VAR_TO_NUM(next->op1.var); |
129 | 12 | if (!zend_bitset_in(def, var_num)) { |
130 | 0 | zend_bitset_incl(use, var_num); |
131 | 0 | } |
132 | 12 | } |
133 | 12 | break; |
134 | 1.19k | case ZEND_ASSIGN_DIM_OP: |
135 | 1.71k | case ZEND_ASSIGN_OBJ_OP: |
136 | 1.71k | next = opline + 1; |
137 | 1.71k | if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { |
138 | 814 | var_num = EX_VAR_TO_NUM(next->op1.var); |
139 | 814 | if (!zend_bitset_in(def, var_num)) { |
140 | 79 | zend_bitset_incl(use, var_num); |
141 | 79 | } |
142 | 814 | } |
143 | 1.71k | if (opline->op1_type == IS_CV) { |
144 | 1.22k | goto add_op1_def; |
145 | 1.22k | } |
146 | 497 | break; |
147 | 4.66k | case ZEND_ASSIGN_OP: |
148 | 8.77k | case ZEND_PRE_INC: |
149 | 9.27k | case ZEND_PRE_DEC: |
150 | 10.0k | case ZEND_POST_INC: |
151 | 11.2k | case ZEND_POST_DEC: |
152 | 11.9k | case ZEND_BIND_GLOBAL: |
153 | 17.8k | case ZEND_BIND_STATIC: |
154 | 17.9k | case ZEND_BIND_INIT_STATIC_OR_JMP: |
155 | 18.4k | case ZEND_SEND_VAR_NO_REF: |
156 | 21.4k | case ZEND_SEND_VAR_NO_REF_EX: |
157 | 27.6k | case ZEND_SEND_VAR_EX: |
158 | 28.7k | case ZEND_SEND_FUNC_ARG: |
159 | 30.9k | case ZEND_SEND_REF: |
160 | 31.6k | case ZEND_SEND_UNPACK: |
161 | 32.2k | case ZEND_FE_RESET_RW: |
162 | 33.1k | case ZEND_MAKE_REF: |
163 | 33.5k | case ZEND_PRE_INC_OBJ: |
164 | 33.7k | case ZEND_PRE_DEC_OBJ: |
165 | 33.9k | case ZEND_POST_INC_OBJ: |
166 | 34.0k | case ZEND_POST_DEC_OBJ: |
167 | 34.8k | case ZEND_UNSET_DIM: |
168 | 35.6k | case ZEND_UNSET_OBJ: |
169 | 37.7k | case ZEND_FETCH_DIM_W: |
170 | 38.4k | case ZEND_FETCH_DIM_RW: |
171 | 39.1k | case ZEND_FETCH_DIM_FUNC_ARG: |
172 | 39.2k | case ZEND_FETCH_DIM_UNSET: |
173 | 39.5k | case ZEND_FETCH_LIST_W: |
174 | 39.5k | if (opline->op1_type == IS_CV) { |
175 | 31.3k | goto add_op1_def; |
176 | 31.3k | } |
177 | 8.17k | break; |
178 | 32.4k | case ZEND_SEND_VAR: |
179 | 33.5k | case ZEND_CAST: |
180 | 39.8k | case ZEND_QM_ASSIGN: |
181 | 41.0k | case ZEND_JMP_SET: |
182 | 42.2k | case ZEND_COALESCE: |
183 | 44.8k | case ZEND_FE_RESET_R: |
184 | 44.8k | if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op1_type == IS_CV) { |
185 | 0 | goto add_op1_def; |
186 | 0 | } |
187 | 44.8k | break; |
188 | 44.8k | case ZEND_ADD_ARRAY_UNPACK: |
189 | 150 | var_num = EX_VAR_TO_NUM(opline->result.var); |
190 | 150 | if (!zend_bitset_in(def, var_num)) { |
191 | 0 | zend_bitset_incl(use, var_num); |
192 | 0 | } |
193 | 150 | break; |
194 | 17.4k | case ZEND_ADD_ARRAY_ELEMENT: |
195 | 17.4k | var_num = EX_VAR_TO_NUM(opline->result.var); |
196 | 17.4k | if (!zend_bitset_in(def, var_num)) { |
197 | 742 | zend_bitset_incl(use, var_num); |
198 | 742 | } |
199 | 17.4k | ZEND_FALLTHROUGH; |
200 | 21.1k | case ZEND_INIT_ARRAY: |
201 | 21.1k | if (((build_flags & ZEND_SSA_RC_INFERENCE) |
202 | 21.1k | || (opline->extended_value & ZEND_ARRAY_ELEMENT_REF)) |
203 | 21.1k | && opline->op1_type == IS_CV) { |
204 | 203 | goto add_op1_def; |
205 | 203 | } |
206 | 20.9k | break; |
207 | 20.9k | case ZEND_YIELD: |
208 | 1.83k | if (opline->op1_type == IS_CV |
209 | 1.83k | && ((op_array->fn_flags & ZEND_ACC_RETURN_REFERENCE) |
210 | 385 | || (build_flags & ZEND_SSA_RC_INFERENCE))) { |
211 | 52 | goto add_op1_def; |
212 | 52 | } |
213 | 1.78k | break; |
214 | 1.78k | case ZEND_UNSET_CV: |
215 | 1.58k | goto add_op1_def; |
216 | 3.23k | case ZEND_VERIFY_RETURN_TYPE: |
217 | 3.23k | if (opline->op1_type & (IS_TMP_VAR|IS_VAR|IS_CV)) { |
218 | 1.60k | goto add_op1_def; |
219 | 1.60k | } |
220 | 1.63k | break; |
221 | 2.59k | case ZEND_FE_FETCH_R: |
222 | 3.23k | 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 | 3.23k | zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var)); |
230 | 3.23k | break; |
231 | 5.45k | case ZEND_BIND_LEXICAL: |
232 | 5.45k | if ((opline->extended_value & ZEND_BIND_REF) || (build_flags & ZEND_SSA_RC_INFERENCE)) { |
233 | 480 | zend_bitset_incl(def, EX_VAR_TO_NUM(opline->op2.var)); |
234 | 480 | } |
235 | 5.45k | break; |
236 | 1.13M | default: |
237 | 1.13M | break; |
238 | 1.33M | } |
239 | | |
240 | 1.33M | if (opline->result_type & (IS_CV|IS_VAR|IS_TMP_VAR)) { |
241 | 737k | zend_bitset_incl(def, EX_VAR_TO_NUM(opline->result.var)); |
242 | 737k | } |
243 | 1.33M | } |
244 | | /* }}} */ |
245 | | |
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 | 0 | { |
248 | 0 | _zend_dfg_add_use_def_op(op_array, opline, build_flags, use, def); |
249 | 0 | } |
250 | | /* }}} */ |
251 | | |
252 | | void zend_build_dfg(const zend_op_array *op_array, const zend_cfg *cfg, zend_dfg *dfg, uint32_t build_flags) /* {{{ */ |
253 | 74.1k | { |
254 | 74.1k | int set_size; |
255 | 74.1k | zend_basic_block *blocks = cfg->blocks; |
256 | 74.1k | int blocks_count = cfg->blocks_count; |
257 | 74.1k | zend_bitset tmp, def, use, in, out; |
258 | 74.1k | int k; |
259 | 74.1k | int j; |
260 | | |
261 | 74.1k | set_size = dfg->size; |
262 | 74.1k | tmp = dfg->tmp; |
263 | 74.1k | def = dfg->def; |
264 | 74.1k | use = dfg->use; |
265 | 74.1k | in = dfg->in; |
266 | 74.1k | out = dfg->out; |
267 | | |
268 | | /* Collect "def" and "use" sets */ |
269 | 290k | for (j = 0; j < blocks_count; j++) { |
270 | 216k | zend_op *opline, *end; |
271 | 216k | zend_bitset b_use, b_def; |
272 | | |
273 | 216k | if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { |
274 | 32 | continue; |
275 | 32 | } |
276 | | |
277 | 216k | opline = op_array->opcodes + blocks[j].start; |
278 | 216k | end = opline + blocks[j].len; |
279 | 216k | b_use = DFG_BITSET(use, set_size, j); |
280 | 216k | b_def = DFG_BITSET(def, set_size, j); |
281 | 1.56M | for (; opline < end; opline++) { |
282 | 1.34M | if (opline->opcode != ZEND_OP_DATA) { |
283 | 1.33M | _zend_dfg_add_use_def_op(op_array, opline, build_flags, b_use, b_def); |
284 | 1.33M | } |
285 | 1.34M | } |
286 | 216k | } |
287 | | |
288 | | /* Calculate "in" and "out" sets */ |
289 | 74.1k | { |
290 | 74.1k | uint32_t worklist_len = zend_bitset_len(blocks_count); |
291 | 74.1k | zend_bitset worklist; |
292 | 74.1k | ALLOCA_FLAG(use_heap); |
293 | 74.1k | worklist = ZEND_BITSET_ALLOCA(worklist_len, use_heap); |
294 | 74.1k | memset(worklist, 0, worklist_len * ZEND_BITSET_ELM_SIZE); |
295 | 290k | for (j = 0; j < blocks_count; j++) { |
296 | 216k | zend_bitset_incl(worklist, j); |
297 | 216k | } |
298 | 335k | 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 | 261k | j = zend_bitset_last(worklist, worklist_len); |
302 | 261k | zend_bitset_excl(worklist, j); |
303 | | |
304 | 261k | if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { |
305 | 32 | continue; |
306 | 32 | } |
307 | 261k | if (blocks[j].successors_count != 0) { |
308 | 186k | zend_bitset_copy(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[0]), set_size); |
309 | 279k | for (k = 1; k < blocks[j].successors_count; k++) { |
310 | 93.3k | zend_bitset_union(DFG_BITSET(out, set_size, j), DFG_BITSET(in, set_size, blocks[j].successors[k]), set_size); |
311 | 93.3k | } |
312 | 186k | } else { |
313 | 75.2k | zend_bitset_clear(DFG_BITSET(out, set_size, j), set_size); |
314 | 75.2k | } |
315 | 261k | 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 | 261k | if (!zend_bitset_equal(DFG_BITSET(in, set_size, j), tmp, set_size)) { |
317 | 192k | zend_bitset_copy(DFG_BITSET(in, set_size, j), tmp, set_size); |
318 | | |
319 | | /* Add predecessors of changed block to worklist */ |
320 | 192k | { |
321 | 192k | int *predecessors = &cfg->predecessors[blocks[j].predecessor_offset]; |
322 | 440k | for (k = 0; k < blocks[j].predecessors_count; k++) { |
323 | 247k | zend_bitset_incl(worklist, predecessors[k]); |
324 | 247k | } |
325 | 192k | } |
326 | 192k | } |
327 | 261k | } |
328 | | |
329 | 74.1k | free_alloca(worklist, use_heap); |
330 | 74.1k | } |
331 | 74.1k | } |
332 | | /* }}} */ |