/src/php-src/Zend/Optimizer/zend_cfg.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | +----------------------------------------------------------------------+ |
3 | | | Zend Engine, CFG - Control 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_cfg.h" |
21 | | #include "zend_func_info.h" |
22 | | #include "zend_worklist.h" |
23 | | #include "zend_optimizer.h" |
24 | | #include "zend_optimizer_internal.h" |
25 | | #include "zend_sort.h" |
26 | | |
27 | | static void zend_mark_reachable(zend_op *opcodes, zend_cfg *cfg, zend_basic_block *b) /* {{{ */ |
28 | 443k | { |
29 | 443k | zend_basic_block *blocks = cfg->blocks; |
30 | | |
31 | 443k | zend_worklist work; |
32 | 443k | ALLOCA_FLAG(list_use_heap) |
33 | 443k | ZEND_WORKLIST_ALLOCA(&work, cfg->blocks_count, list_use_heap); |
34 | | |
35 | 443k | zend_worklist_push(&work, b - cfg->blocks); |
36 | | |
37 | 1.75M | while (zend_worklist_len(&work)) { |
38 | 1.31M | int i; |
39 | 1.31M | b = cfg->blocks + zend_worklist_pop(&work); |
40 | | |
41 | 1.31M | b->flags |= ZEND_BB_REACHABLE; |
42 | 1.31M | if (b->successors_count == 0) { |
43 | 371k | b->flags |= ZEND_BB_EXIT; |
44 | 371k | continue; |
45 | 371k | } |
46 | | |
47 | 2.23M | for (i = 0; i < b->successors_count; i++) { |
48 | 1.29M | zend_basic_block *succ = blocks + b->successors[i]; |
49 | | |
50 | 1.29M | if (b->len != 0) { |
51 | 1.29M | uint8_t opcode = opcodes[b->start + b->len - 1].opcode; |
52 | 1.29M | if (opcode == ZEND_MATCH) { |
53 | 3.10k | succ->flags |= ZEND_BB_TARGET; |
54 | 1.29M | } else if (opcode == ZEND_SWITCH_LONG || opcode == ZEND_SWITCH_STRING) { |
55 | 1.03k | if (i == b->successors_count - 1) { |
56 | 185 | succ->flags |= ZEND_BB_FOLLOW | ZEND_BB_TARGET; |
57 | 848 | } else { |
58 | 848 | succ->flags |= ZEND_BB_TARGET; |
59 | 848 | } |
60 | 1.29M | } else if (b->successors_count == 1) { |
61 | 589k | if (opcode == ZEND_JMP) { |
62 | 177k | succ->flags |= ZEND_BB_TARGET; |
63 | 411k | } else { |
64 | 411k | succ->flags |= ZEND_BB_FOLLOW; |
65 | | |
66 | 411k | if ((cfg->flags & ZEND_CFG_STACKLESS)) { |
67 | 0 | if (opcode == ZEND_INCLUDE_OR_EVAL || |
68 | 0 | opcode == ZEND_GENERATOR_CREATE || |
69 | 0 | opcode == ZEND_YIELD || |
70 | 0 | opcode == ZEND_YIELD_FROM || |
71 | 0 | opcode == ZEND_DO_FCALL || |
72 | 0 | opcode == ZEND_DO_UCALL || |
73 | 0 | opcode == ZEND_DO_FCALL_BY_NAME) { |
74 | 0 | succ->flags |= ZEND_BB_ENTRY; |
75 | 0 | } |
76 | 0 | } |
77 | 411k | if ((cfg->flags & ZEND_CFG_RECV_ENTRY)) { |
78 | 0 | if (opcode == ZEND_RECV || |
79 | 0 | opcode == ZEND_RECV_INIT) { |
80 | 0 | succ->flags |= ZEND_BB_RECV_ENTRY; |
81 | 0 | } |
82 | 0 | } |
83 | 411k | } |
84 | 701k | } else { |
85 | 701k | ZEND_ASSERT(b->successors_count == 2); |
86 | 701k | if (i == 0) { |
87 | 350k | succ->flags |= ZEND_BB_TARGET; |
88 | 350k | } else { |
89 | 350k | succ->flags |= ZEND_BB_FOLLOW; |
90 | 350k | } |
91 | 701k | } |
92 | 1.29M | } else { |
93 | 777 | succ->flags |= ZEND_BB_FOLLOW; |
94 | 777 | } |
95 | | |
96 | | /* Check reachability of successor */ |
97 | 1.29M | if (!(succ->flags & ZEND_BB_REACHABLE)) { |
98 | 1.08M | zend_worklist_push(&work, succ - cfg->blocks); |
99 | 1.08M | } |
100 | 1.29M | } |
101 | 941k | } |
102 | | |
103 | 443k | ZEND_WORKLIST_FREE_ALLOCA(&work, list_use_heap); |
104 | 443k | } |
105 | | /* }}} */ |
106 | | |
107 | | static void zend_mark_reachable_blocks(const zend_op_array *op_array, zend_cfg *cfg, int start) /* {{{ */ |
108 | 327k | { |
109 | 327k | zend_basic_block *blocks = cfg->blocks; |
110 | | |
111 | 327k | blocks[start].flags = ZEND_BB_START; |
112 | 327k | zend_mark_reachable(op_array->opcodes, cfg, blocks + start); |
113 | | |
114 | 327k | if (op_array->last_try_catch) { |
115 | 96.1k | zend_basic_block *b; |
116 | 96.1k | int j, changed; |
117 | 96.1k | uint32_t *block_map = cfg->map; |
118 | | |
119 | 191k | do { |
120 | 191k | changed = 0; |
121 | | |
122 | | /* Add exception paths */ |
123 | 424k | for (j = 0; j < op_array->last_try_catch; j++) { |
124 | | |
125 | | /* check for jumps into the middle of try block */ |
126 | 232k | b = blocks + block_map[op_array->try_catch_array[j].try_op]; |
127 | 232k | if (!(b->flags & ZEND_BB_REACHABLE)) { |
128 | 65 | zend_basic_block *end; |
129 | | |
130 | 65 | if (op_array->try_catch_array[j].catch_op) { |
131 | 65 | end = blocks + block_map[op_array->try_catch_array[j].catch_op]; |
132 | 234 | while (b != end) { |
133 | 182 | if (b->flags & ZEND_BB_REACHABLE) { |
134 | 13 | op_array->try_catch_array[j].try_op = b->start; |
135 | 13 | break; |
136 | 13 | } |
137 | 169 | b++; |
138 | 169 | } |
139 | 65 | } |
140 | 65 | b = blocks + block_map[op_array->try_catch_array[j].try_op]; |
141 | 65 | if (!(b->flags & ZEND_BB_REACHABLE)) { |
142 | 52 | if (op_array->try_catch_array[j].finally_op) { |
143 | 12 | end = blocks + block_map[op_array->try_catch_array[j].finally_op]; |
144 | 44 | while (b != end) { |
145 | 44 | if (b->flags & ZEND_BB_REACHABLE) { |
146 | | /* In case we get here, there is no live try block but there is a live finally block. |
147 | | * If we do have catch_op set, we need to set it to the first catch block to satisfy |
148 | | * the constraint try_op <= catch_op <= finally_op */ |
149 | 12 | op_array->try_catch_array[j].try_op = |
150 | 12 | op_array->try_catch_array[j].catch_op ? op_array->try_catch_array[j].catch_op : b->start; |
151 | 12 | changed = 1; |
152 | 12 | zend_mark_reachable(op_array->opcodes, cfg, blocks + block_map[op_array->try_catch_array[j].try_op]); |
153 | 12 | break; |
154 | 12 | } |
155 | 32 | b++; |
156 | 32 | } |
157 | 12 | } |
158 | 52 | } |
159 | 65 | } |
160 | | |
161 | 232k | b = blocks + block_map[op_array->try_catch_array[j].try_op]; |
162 | 232k | if (b->flags & ZEND_BB_REACHABLE) { |
163 | 232k | b->flags |= ZEND_BB_TRY; |
164 | 232k | if (op_array->try_catch_array[j].catch_op) { |
165 | 230k | b = blocks + block_map[op_array->try_catch_array[j].catch_op]; |
166 | 230k | b->flags |= ZEND_BB_CATCH; |
167 | 230k | if (!(b->flags & ZEND_BB_REACHABLE)) { |
168 | 115k | changed = 1; |
169 | 115k | zend_mark_reachable(op_array->opcodes, cfg, b); |
170 | 115k | } |
171 | 230k | } |
172 | 232k | if (op_array->try_catch_array[j].finally_op) { |
173 | 2.80k | b = blocks + block_map[op_array->try_catch_array[j].finally_op]; |
174 | 2.80k | b->flags |= ZEND_BB_FINALLY; |
175 | 2.80k | if (!(b->flags & ZEND_BB_REACHABLE)) { |
176 | 346 | changed = 1; |
177 | 346 | zend_mark_reachable(op_array->opcodes, cfg, b); |
178 | 346 | } |
179 | 2.80k | } |
180 | 232k | if (op_array->try_catch_array[j].finally_end) { |
181 | 2.80k | b = blocks + block_map[op_array->try_catch_array[j].finally_end]; |
182 | 2.80k | b->flags |= ZEND_BB_FINALLY_END; |
183 | 2.80k | if (!(b->flags & ZEND_BB_REACHABLE)) { |
184 | 510 | changed = 1; |
185 | 510 | zend_mark_reachable(op_array->opcodes, cfg, b); |
186 | 510 | } |
187 | 2.80k | } |
188 | 232k | } else { |
189 | 40 | if (op_array->try_catch_array[j].catch_op) { |
190 | 40 | ZEND_ASSERT(!(blocks[block_map[op_array->try_catch_array[j].catch_op]].flags & ZEND_BB_REACHABLE)); |
191 | 40 | } |
192 | 40 | if (op_array->try_catch_array[j].finally_op) { |
193 | 0 | ZEND_ASSERT(!(blocks[block_map[op_array->try_catch_array[j].finally_op]].flags & ZEND_BB_REACHABLE)); |
194 | 0 | } |
195 | 40 | if (op_array->try_catch_array[j].finally_end) { |
196 | 0 | ZEND_ASSERT(!(blocks[block_map[op_array->try_catch_array[j].finally_end]].flags & ZEND_BB_REACHABLE)); |
197 | 0 | } |
198 | 40 | } |
199 | 232k | } |
200 | 191k | } while (changed); |
201 | 96.1k | } |
202 | | |
203 | 327k | if (cfg->flags & ZEND_FUNC_FREE_LOOP_VAR) { |
204 | 44.4k | zend_basic_block *b; |
205 | 44.4k | int j; |
206 | 44.4k | uint32_t *block_map = cfg->map; |
207 | | |
208 | | /* Mark blocks that are unreachable, but free a loop var created in a reachable block. */ |
209 | 502k | for (b = blocks; b < blocks + cfg->blocks_count; b++) { |
210 | 458k | if (b->flags & ZEND_BB_REACHABLE) { |
211 | 442k | continue; |
212 | 442k | } |
213 | | |
214 | 18.6k | for (j = b->start; j < b->start + b->len; j++) { |
215 | 2.83k | zend_op *opline = &op_array->opcodes[j]; |
216 | 2.83k | if (zend_optimizer_is_loop_var_free(opline)) { |
217 | 120 | zend_op *def_opline = zend_optimizer_get_loop_var_def(op_array, opline); |
218 | 120 | if (def_opline) { |
219 | 118 | uint32_t def_block = block_map[def_opline - op_array->opcodes]; |
220 | 118 | if (blocks[def_block].flags & ZEND_BB_REACHABLE) { |
221 | 102 | b->flags |= ZEND_BB_UNREACHABLE_FREE; |
222 | 102 | break; |
223 | 102 | } |
224 | 118 | } |
225 | 120 | } |
226 | 2.83k | } |
227 | 15.9k | } |
228 | 44.4k | } |
229 | 327k | } |
230 | | /* }}} */ |
231 | | |
232 | | void zend_cfg_remark_reachable_blocks(const zend_op_array *op_array, zend_cfg *cfg) /* {{{ */ |
233 | 141k | { |
234 | 141k | zend_basic_block *blocks = cfg->blocks; |
235 | 141k | int i; |
236 | 141k | int start = 0; |
237 | | |
238 | 141k | for (i = 0; i < cfg->blocks_count; i++) { |
239 | 141k | if (blocks[i].flags & ZEND_BB_REACHABLE) { |
240 | 141k | start = i; |
241 | 141k | i++; |
242 | 141k | break; |
243 | 141k | } |
244 | 141k | } |
245 | | |
246 | | /* clear all flags */ |
247 | 841k | for (i = 0; i < cfg->blocks_count; i++) { |
248 | 699k | blocks[i].flags = 0; |
249 | 699k | } |
250 | | |
251 | 141k | zend_mark_reachable_blocks(op_array, cfg, start); |
252 | 141k | } |
253 | | /* }}} */ |
254 | | |
255 | 689k | static void initialize_block(zend_basic_block *block) { |
256 | 689k | block->flags = 0; |
257 | 689k | block->successors = block->successors_storage; |
258 | 689k | block->successors_count = 0; |
259 | 689k | block->predecessors_count = 0; |
260 | 689k | block->predecessor_offset = -1; |
261 | 689k | block->idom = -1; |
262 | 689k | block->loop_header = -1; |
263 | 689k | block->level = -1; |
264 | 689k | block->children = -1; |
265 | 689k | block->next_child = -1; |
266 | 689k | } |
267 | | |
268 | 879k | #define BB_START(i) do { \ |
269 | 879k | if (!block_map[i]) { blocks_count++;} \ |
270 | 879k | block_map[i]++; \ |
271 | 879k | } while (0) |
272 | | |
273 | | ZEND_API void zend_build_cfg(zend_arena **arena, const zend_op_array *op_array, uint32_t build_flags, zend_cfg *cfg) /* {{{ */ |
274 | 185k | { |
275 | 185k | uint32_t flags = 0; |
276 | 185k | uint32_t i; |
277 | 185k | int j; |
278 | 185k | uint32_t *block_map; |
279 | 185k | zend_function *fn; |
280 | 185k | int blocks_count = 0; |
281 | 185k | zend_basic_block *blocks; |
282 | 185k | zval *zv; |
283 | 185k | bool extra_entry_block = 0; |
284 | | |
285 | 185k | cfg->flags = build_flags & (ZEND_CFG_STACKLESS|ZEND_CFG_RECV_ENTRY); |
286 | | |
287 | 185k | cfg->map = block_map = zend_arena_calloc(arena, op_array->last, sizeof(uint32_t)); |
288 | | |
289 | | /* Build CFG, Step 1: Find basic blocks starts, calculate number of blocks */ |
290 | 185k | BB_START(0); |
291 | 4.16M | for (i = 0; i < op_array->last; i++) { |
292 | 3.97M | zend_op *opline = op_array->opcodes + i; |
293 | 3.97M | switch (opline->opcode) { |
294 | 42.0k | case ZEND_RECV: |
295 | 47.6k | case ZEND_RECV_INIT: |
296 | 47.6k | if (build_flags & ZEND_CFG_RECV_ENTRY) { |
297 | 0 | BB_START(i + 1); |
298 | 0 | } |
299 | 47.6k | break; |
300 | 204k | case ZEND_RETURN: |
301 | 206k | case ZEND_RETURN_BY_REF: |
302 | 210k | case ZEND_GENERATOR_RETURN: |
303 | 210k | case ZEND_VERIFY_NEVER_TYPE: |
304 | 210k | if (i + 1 < op_array->last) { |
305 | 27.1k | BB_START(i + 1); |
306 | 27.1k | } |
307 | 210k | break; |
308 | 716 | case ZEND_MATCH_ERROR: |
309 | 4.92k | case ZEND_THROW: |
310 | | /* Don't treat THROW as terminator if it's used in expression context, |
311 | | * as we may lose live ranges when eliminating unreachable code. */ |
312 | 4.92k | if (opline->extended_value != ZEND_THROW_IS_EXPR && i + 1 < op_array->last) { |
313 | 3.13k | BB_START(i + 1); |
314 | 3.13k | } |
315 | 4.92k | break; |
316 | 11.1k | case ZEND_INCLUDE_OR_EVAL: |
317 | 11.1k | flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS; |
318 | 11.1k | ZEND_FALLTHROUGH; |
319 | 14.6k | case ZEND_GENERATOR_CREATE: |
320 | 18.6k | case ZEND_YIELD: |
321 | 19.6k | case ZEND_YIELD_FROM: |
322 | 19.6k | if (build_flags & ZEND_CFG_STACKLESS) { |
323 | 0 | BB_START(i + 1); |
324 | 0 | } |
325 | 19.6k | break; |
326 | 366k | case ZEND_DO_FCALL: |
327 | 385k | case ZEND_DO_UCALL: |
328 | 386k | case ZEND_DO_FCALL_BY_NAME: |
329 | 386k | flags |= ZEND_FUNC_HAS_CALLS; |
330 | 386k | if (build_flags & ZEND_CFG_STACKLESS) { |
331 | 0 | BB_START(i + 1); |
332 | 0 | } |
333 | 386k | break; |
334 | 0 | case ZEND_DO_ICALL: |
335 | 0 | flags |= ZEND_FUNC_HAS_CALLS; |
336 | 0 | break; |
337 | 189k | case ZEND_INIT_FCALL: |
338 | 194k | case ZEND_INIT_NS_FCALL_BY_NAME: |
339 | 194k | zv = CRT_CONSTANT(opline->op2); |
340 | 194k | if (opline->opcode == ZEND_INIT_NS_FCALL_BY_NAME) { |
341 | | /* The third literal is the lowercased unqualified name */ |
342 | 4.79k | zv += 2; |
343 | 4.79k | } |
344 | 194k | if ((fn = zend_hash_find_ptr(EG(function_table), Z_STR_P(zv))) != NULL) { |
345 | 155k | if (fn->type == ZEND_INTERNAL_FUNCTION) { |
346 | 155k | flags |= zend_optimizer_classify_function( |
347 | 155k | Z_STR_P(zv), opline->extended_value); |
348 | 155k | } |
349 | 155k | } |
350 | 194k | break; |
351 | 900 | case ZEND_FAST_CALL: |
352 | 900 | BB_START(OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes); |
353 | 900 | BB_START(i + 1); |
354 | 900 | break; |
355 | 678 | case ZEND_FAST_RET: |
356 | 678 | if (i + 1 < op_array->last) { |
357 | 678 | BB_START(i + 1); |
358 | 678 | } |
359 | 678 | break; |
360 | 74.6k | case ZEND_JMP: |
361 | 74.6k | BB_START(OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes); |
362 | 74.6k | if (i + 1 < op_array->last) { |
363 | 73.6k | BB_START(i + 1); |
364 | 73.6k | } |
365 | 74.6k | break; |
366 | 23.7k | case ZEND_JMPZ: |
367 | 40.3k | case ZEND_JMPNZ: |
368 | 41.8k | case ZEND_JMPZ_EX: |
369 | 42.9k | case ZEND_JMPNZ_EX: |
370 | 45.4k | case ZEND_JMP_SET: |
371 | 48.3k | case ZEND_COALESCE: |
372 | 50.3k | case ZEND_ASSERT_CHECK: |
373 | 142k | case ZEND_JMP_NULL: |
374 | 143k | case ZEND_BIND_INIT_STATIC_OR_JMP: |
375 | 143k | case ZEND_JMP_FRAMELESS: |
376 | 143k | BB_START(OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes); |
377 | 143k | BB_START(i + 1); |
378 | 143k | break; |
379 | 44.0k | case ZEND_CATCH: |
380 | 44.0k | if (!(opline->extended_value & ZEND_LAST_CATCH)) { |
381 | 5.51k | BB_START(OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes); |
382 | 5.51k | } |
383 | 44.0k | BB_START(i + 1); |
384 | 44.0k | break; |
385 | 17.4k | case ZEND_FE_FETCH_R: |
386 | 18.9k | case ZEND_FE_FETCH_RW: |
387 | 18.9k | BB_START(ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)); |
388 | 18.9k | BB_START(i + 1); |
389 | 18.9k | break; |
390 | 17.4k | case ZEND_FE_RESET_R: |
391 | 18.9k | case ZEND_FE_RESET_RW: |
392 | 18.9k | BB_START(OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes); |
393 | 18.9k | BB_START(i + 1); |
394 | 18.9k | break; |
395 | 16 | case ZEND_SWITCH_LONG: |
396 | 112 | case ZEND_SWITCH_STRING: |
397 | 534 | case ZEND_MATCH: |
398 | 534 | { |
399 | 534 | HashTable *jumptable = Z_ARRVAL_P(CRT_CONSTANT(opline->op2)); |
400 | 534 | zval *zv; |
401 | 4.95k | ZEND_HASH_FOREACH_VAL(jumptable, zv) { |
402 | 4.95k | BB_START(ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, Z_LVAL_P(zv))); |
403 | 4.95k | } ZEND_HASH_FOREACH_END(); |
404 | 534 | BB_START(ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)); |
405 | 534 | BB_START(i + 1); |
406 | 534 | break; |
407 | 112 | } |
408 | 3.92k | case ZEND_FETCH_R: |
409 | 6.91k | case ZEND_FETCH_W: |
410 | 7.94k | case ZEND_FETCH_RW: |
411 | 8.02k | case ZEND_FETCH_FUNC_ARG: |
412 | 8.10k | case ZEND_FETCH_IS: |
413 | 8.14k | case ZEND_FETCH_UNSET: |
414 | 8.47k | case ZEND_UNSET_VAR: |
415 | 8.79k | case ZEND_ISSET_ISEMPTY_VAR: |
416 | 8.79k | if (opline->extended_value & ZEND_FETCH_LOCAL) { |
417 | 6.54k | flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS; |
418 | 6.54k | } else if ((opline->extended_value & (ZEND_FETCH_GLOBAL | ZEND_FETCH_GLOBAL_LOCK)) && |
419 | 2.25k | !op_array->function_name) { |
420 | 632 | flags |= ZEND_FUNC_INDIRECT_VAR_ACCESS; |
421 | 632 | } |
422 | 8.79k | break; |
423 | 270 | case ZEND_FUNC_GET_ARGS: |
424 | 270 | flags |= ZEND_FUNC_VARARG; |
425 | 270 | break; |
426 | 0 | case ZEND_EXT_STMT: |
427 | 0 | flags |= ZEND_FUNC_HAS_EXTENDED_STMT; |
428 | 0 | break; |
429 | 0 | case ZEND_EXT_FCALL_BEGIN: |
430 | 0 | case ZEND_EXT_FCALL_END: |
431 | 0 | flags |= ZEND_FUNC_HAS_EXTENDED_FCALL; |
432 | 0 | break; |
433 | 52.5k | case ZEND_FREE: |
434 | 71.7k | case ZEND_FE_FREE: |
435 | 71.7k | if (zend_optimizer_is_loop_var_free(opline) |
436 | 71.7k | && ((opline-1)->opcode != ZEND_MATCH_ERROR |
437 | 19.4k | || (opline-1)->extended_value != ZEND_THROW_IS_EXPR)) { |
438 | 19.4k | BB_START(i); |
439 | 19.4k | flags |= ZEND_FUNC_FREE_LOOP_VAR; |
440 | 19.4k | } |
441 | 71.7k | break; |
442 | 3.97M | } |
443 | 3.97M | } |
444 | | |
445 | | /* If the entry block has predecessors, we may need to split it */ |
446 | 185k | if ((build_flags & ZEND_CFG_NO_ENTRY_PREDECESSORS) |
447 | 185k | && op_array->last > 0 && block_map[0] > 1) { |
448 | 139 | extra_entry_block = 1; |
449 | 139 | } |
450 | | |
451 | 185k | if (op_array->last_try_catch) { |
452 | 71.3k | for (j = 0; j < op_array->last_try_catch; j++) { |
453 | 39.1k | BB_START(op_array->try_catch_array[j].try_op); |
454 | 39.1k | if (op_array->try_catch_array[j].catch_op) { |
455 | 38.5k | BB_START(op_array->try_catch_array[j].catch_op); |
456 | 38.5k | } |
457 | 39.1k | if (op_array->try_catch_array[j].finally_op) { |
458 | 678 | BB_START(op_array->try_catch_array[j].finally_op); |
459 | 678 | } |
460 | 39.1k | if (op_array->try_catch_array[j].finally_end) { |
461 | 678 | BB_START(op_array->try_catch_array[j].finally_end); |
462 | 678 | } |
463 | 39.1k | } |
464 | 32.2k | } |
465 | | |
466 | 185k | blocks_count += extra_entry_block; |
467 | 185k | cfg->blocks_count = blocks_count; |
468 | | |
469 | | /* Build CFG, Step 2: Build Array of Basic Blocks */ |
470 | 185k | cfg->blocks = blocks = zend_arena_calloc(arena, sizeof(zend_basic_block), blocks_count); |
471 | | |
472 | 185k | blocks_count = -1; |
473 | | |
474 | 185k | if (extra_entry_block) { |
475 | 139 | initialize_block(&blocks[0]); |
476 | 139 | blocks[0].start = 0; |
477 | 139 | blocks[0].len = 0; |
478 | 139 | blocks_count++; |
479 | 139 | } |
480 | | |
481 | 4.16M | for (i = 0; i < op_array->last; i++) { |
482 | 3.97M | if (block_map[i]) { |
483 | 689k | if (blocks_count >= 0) { |
484 | 503k | blocks[blocks_count].len = i - blocks[blocks_count].start; |
485 | 503k | } |
486 | 689k | blocks_count++; |
487 | 689k | initialize_block(&blocks[blocks_count]); |
488 | 689k | blocks[blocks_count].start = i; |
489 | 689k | } |
490 | 3.97M | block_map[i] = blocks_count; |
491 | 3.97M | } |
492 | | |
493 | 185k | blocks[blocks_count].len = i - blocks[blocks_count].start; |
494 | 185k | blocks_count++; |
495 | | |
496 | | /* Build CFG, Step 3: Calculate successors */ |
497 | 875k | for (j = 0; j < blocks_count; j++) { |
498 | 689k | zend_basic_block *block = &blocks[j]; |
499 | 689k | zend_op *opline; |
500 | 689k | if (block->len == 0) { |
501 | 139 | block->successors_count = 1; |
502 | 139 | block->successors[0] = j + 1; |
503 | 139 | continue; |
504 | 139 | } |
505 | | |
506 | 689k | opline = op_array->opcodes + block->start + block->len - 1; |
507 | 689k | switch (opline->opcode) { |
508 | 678 | case ZEND_FAST_RET: |
509 | 205k | case ZEND_RETURN: |
510 | 207k | case ZEND_RETURN_BY_REF: |
511 | 211k | case ZEND_GENERATOR_RETURN: |
512 | 215k | case ZEND_THROW: |
513 | 215k | case ZEND_MATCH_ERROR: |
514 | 215k | case ZEND_VERIFY_NEVER_TYPE: |
515 | 215k | break; |
516 | 74.6k | case ZEND_JMP: |
517 | 74.6k | block->successors_count = 1; |
518 | 74.6k | block->successors[0] = block_map[OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes]; |
519 | 74.6k | break; |
520 | 23.7k | case ZEND_JMPZ: |
521 | 40.3k | case ZEND_JMPNZ: |
522 | 41.8k | case ZEND_JMPZ_EX: |
523 | 42.9k | case ZEND_JMPNZ_EX: |
524 | 45.4k | case ZEND_JMP_SET: |
525 | 48.3k | case ZEND_COALESCE: |
526 | 50.3k | case ZEND_ASSERT_CHECK: |
527 | 142k | case ZEND_JMP_NULL: |
528 | 143k | case ZEND_BIND_INIT_STATIC_OR_JMP: |
529 | 143k | case ZEND_JMP_FRAMELESS: |
530 | 143k | block->successors_count = 2; |
531 | 143k | block->successors[0] = block_map[OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes]; |
532 | 143k | block->successors[1] = j + 1; |
533 | 143k | break; |
534 | 44.0k | case ZEND_CATCH: |
535 | 44.0k | if (!(opline->extended_value & ZEND_LAST_CATCH)) { |
536 | 5.51k | block->successors_count = 2; |
537 | 5.51k | block->successors[0] = block_map[OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes]; |
538 | 5.51k | block->successors[1] = j + 1; |
539 | 38.5k | } else { |
540 | 38.5k | block->successors_count = 1; |
541 | 38.5k | block->successors[0] = j + 1; |
542 | 38.5k | } |
543 | 44.0k | break; |
544 | 17.4k | case ZEND_FE_FETCH_R: |
545 | 18.9k | case ZEND_FE_FETCH_RW: |
546 | 18.9k | block->successors_count = 2; |
547 | 18.9k | block->successors[0] = block_map[ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)]; |
548 | 18.9k | block->successors[1] = j + 1; |
549 | 18.9k | break; |
550 | 17.4k | case ZEND_FE_RESET_R: |
551 | 18.9k | case ZEND_FE_RESET_RW: |
552 | 18.9k | block->successors_count = 2; |
553 | 18.9k | block->successors[0] = block_map[OP_JMP_ADDR(opline, opline->op2) - op_array->opcodes]; |
554 | 18.9k | block->successors[1] = j + 1; |
555 | 18.9k | break; |
556 | 900 | case ZEND_FAST_CALL: |
557 | 900 | block->successors_count = 2; |
558 | 900 | block->successors[0] = block_map[OP_JMP_ADDR(opline, opline->op1) - op_array->opcodes]; |
559 | 900 | block->successors[1] = j + 1; |
560 | 900 | break; |
561 | 16 | case ZEND_SWITCH_LONG: |
562 | 112 | case ZEND_SWITCH_STRING: |
563 | 534 | case ZEND_MATCH: |
564 | 534 | { |
565 | 534 | HashTable *jumptable = Z_ARRVAL_P(CRT_CONSTANT(opline->op2)); |
566 | 534 | zval *zv; |
567 | 534 | uint32_t s = 0; |
568 | | |
569 | 534 | block->successors_count = (opline->opcode == ZEND_MATCH ? 1 : 2) + zend_hash_num_elements(jumptable); |
570 | 534 | block->successors = zend_arena_calloc(arena, block->successors_count, sizeof(int)); |
571 | | |
572 | 4.95k | ZEND_HASH_FOREACH_VAL(jumptable, zv) { |
573 | 4.95k | block->successors[s++] = block_map[ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, Z_LVAL_P(zv))]; |
574 | 4.95k | } ZEND_HASH_FOREACH_END(); |
575 | | |
576 | 534 | block->successors[s++] = block_map[ZEND_OFFSET_TO_OPLINE_NUM(op_array, opline, opline->extended_value)]; |
577 | 534 | if (opline->opcode != ZEND_MATCH) { |
578 | 112 | block->successors[s++] = j + 1; |
579 | 112 | } |
580 | 534 | break; |
581 | 112 | } |
582 | 172k | default: |
583 | 172k | block->successors_count = 1; |
584 | 172k | block->successors[0] = j + 1; |
585 | 172k | break; |
586 | 689k | } |
587 | 689k | } |
588 | | |
589 | | /* Build CFG, Step 4, Mark Reachable Basic Blocks */ |
590 | 185k | cfg->flags |= flags; |
591 | 185k | zend_mark_reachable_blocks(op_array, cfg, 0); |
592 | 185k | } |
593 | | /* }}} */ |
594 | | |
595 | | ZEND_API void zend_cfg_build_predecessors(zend_arena **arena, zend_cfg *cfg) /* {{{ */ |
596 | 74.1k | { |
597 | 74.1k | int j, s, edges; |
598 | 74.1k | zend_basic_block *b; |
599 | 74.1k | zend_basic_block *blocks = cfg->blocks; |
600 | 74.1k | zend_basic_block *end = blocks + cfg->blocks_count; |
601 | 74.1k | int *predecessors; |
602 | | |
603 | 74.1k | edges = 0; |
604 | 290k | for (b = blocks; b < end; b++) { |
605 | 216k | b->predecessors_count = 0; |
606 | 216k | } |
607 | 290k | for (b = blocks; b < end; b++) { |
608 | 216k | if (!(b->flags & ZEND_BB_REACHABLE)) { |
609 | 32 | b->successors_count = 0; |
610 | 32 | b->predecessors_count = 0; |
611 | 216k | } else { |
612 | 427k | for (s = 0; s < b->successors_count; s++) { |
613 | 211k | edges++; |
614 | 211k | blocks[b->successors[s]].predecessors_count++; |
615 | 211k | } |
616 | 216k | } |
617 | 216k | } |
618 | | |
619 | 74.1k | cfg->edges_count = edges; |
620 | 74.1k | cfg->predecessors = predecessors = (int*)zend_arena_calloc(arena, sizeof(int), edges); |
621 | | |
622 | 74.1k | edges = 0; |
623 | 290k | for (b = blocks; b < end; b++) { |
624 | 216k | if (b->flags & ZEND_BB_REACHABLE) { |
625 | 216k | b->predecessor_offset = edges; |
626 | 216k | edges += b->predecessors_count; |
627 | 216k | b->predecessors_count = 0; |
628 | 216k | } |
629 | 216k | } |
630 | | |
631 | 290k | for (j = 0; j < cfg->blocks_count; j++) { |
632 | 216k | if (blocks[j].flags & ZEND_BB_REACHABLE) { |
633 | | /* SWITCH_STRING/LONG may have few identical successors */ |
634 | 427k | for (s = 0; s < blocks[j].successors_count; s++) { |
635 | 211k | int duplicate = 0; |
636 | 211k | int p; |
637 | | |
638 | 284k | for (p = 0; p < s; p++) { |
639 | 73.1k | if (blocks[j].successors[p] == blocks[j].successors[s]) { |
640 | 236 | duplicate = 1; |
641 | 236 | break; |
642 | 236 | } |
643 | 73.1k | } |
644 | 211k | if (!duplicate) { |
645 | 210k | zend_basic_block *b = blocks + blocks[j].successors[s]; |
646 | | |
647 | 210k | predecessors[b->predecessor_offset + b->predecessors_count] = j; |
648 | 210k | b->predecessors_count++; |
649 | 210k | } |
650 | 211k | } |
651 | 216k | } |
652 | 216k | } |
653 | 74.1k | } |
654 | | /* }}} */ |
655 | | |
656 | | /* Computes a postorder numbering of the CFG */ |
657 | | static void compute_postnum_recursive( |
658 | | int *postnum, int *cur, const zend_cfg *cfg, int block_num) /* {{{ */ |
659 | 222k | { |
660 | 222k | int s; |
661 | 222k | zend_basic_block *block = &cfg->blocks[block_num]; |
662 | 222k | if (postnum[block_num] != -1) { |
663 | 68.7k | return; |
664 | 68.7k | } |
665 | | |
666 | 154k | postnum[block_num] = -2; /* Marker for "currently visiting" */ |
667 | 365k | for (s = 0; s < block->successors_count; s++) { |
668 | 211k | compute_postnum_recursive(postnum, cur, cfg, block->successors[s]); |
669 | 211k | } |
670 | 154k | postnum[block_num] = (*cur)++; |
671 | 154k | } |
672 | | /* }}} */ |
673 | | |
674 | | /* Computes dominator tree using algorithm from "A Simple, Fast Dominance Algorithm" by |
675 | | * Cooper, Harvey and Kennedy. */ |
676 | | ZEND_API void zend_cfg_compute_dominators_tree(const zend_op_array *op_array, zend_cfg *cfg) /* {{{ */ |
677 | 74.1k | { |
678 | 74.1k | zend_basic_block *blocks = cfg->blocks; |
679 | 74.1k | int blocks_count = cfg->blocks_count; |
680 | 74.1k | int j, k, changed; |
681 | | |
682 | 74.1k | if (cfg->blocks_count == 1) { |
683 | 62.5k | blocks[0].level = 0; |
684 | 62.5k | return; |
685 | 62.5k | } |
686 | | |
687 | 11.5k | ALLOCA_FLAG(use_heap) |
688 | 11.5k | int *postnum = do_alloca(sizeof(int) * cfg->blocks_count, use_heap); |
689 | 11.5k | memset(postnum, -1, sizeof(int) * cfg->blocks_count); |
690 | 11.5k | j = 0; |
691 | 11.5k | compute_postnum_recursive(postnum, &j, cfg, 0); |
692 | | |
693 | | /* FIXME: move declarations */ |
694 | 11.5k | blocks[0].idom = 0; |
695 | 28.0k | do { |
696 | 28.0k | changed = 0; |
697 | | /* Iterating in RPO here would converge faster */ |
698 | 369k | for (j = 1; j < blocks_count; j++) { |
699 | 341k | int idom = -1; |
700 | | |
701 | 341k | if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { |
702 | 50 | continue; |
703 | 50 | } |
704 | 843k | for (k = 0; k < blocks[j].predecessors_count; k++) { |
705 | 501k | int pred = cfg->predecessors[blocks[j].predecessor_offset + k]; |
706 | | |
707 | 501k | if (blocks[pred].idom >= 0) { |
708 | 444k | if (idom < 0) { |
709 | 307k | idom = pred; |
710 | 307k | } else { |
711 | 273k | while (idom != pred) { |
712 | 335k | while (postnum[pred] < postnum[idom]) pred = blocks[pred].idom; |
713 | 143k | while (postnum[idom] < postnum[pred]) idom = blocks[idom].idom; |
714 | 137k | } |
715 | 136k | } |
716 | 444k | } |
717 | 501k | } |
718 | | |
719 | 341k | if (idom >= 0 && blocks[j].idom != idom) { |
720 | 142k | blocks[j].idom = idom; |
721 | 142k | changed = 1; |
722 | 142k | } |
723 | 341k | } |
724 | 28.0k | } while (changed); |
725 | 11.5k | blocks[0].idom = -1; |
726 | | |
727 | 154k | for (j = 1; j < blocks_count; j++) { |
728 | 142k | if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { |
729 | 32 | continue; |
730 | 32 | } |
731 | 142k | if (blocks[j].idom >= 0) { |
732 | | /* Sort by block number to traverse children in pre-order */ |
733 | 142k | if (blocks[blocks[j].idom].children < 0 || |
734 | 142k | j < blocks[blocks[j].idom].children) { |
735 | 75.3k | blocks[j].next_child = blocks[blocks[j].idom].children; |
736 | 75.3k | blocks[blocks[j].idom].children = j; |
737 | 75.3k | } else { |
738 | 67.1k | int k = blocks[blocks[j].idom].children; |
739 | 73.3k | while (blocks[k].next_child >=0 && j > blocks[k].next_child) { |
740 | 6.25k | k = blocks[k].next_child; |
741 | 6.25k | } |
742 | 67.1k | blocks[j].next_child = blocks[k].next_child; |
743 | 67.1k | blocks[k].next_child = j; |
744 | 67.1k | } |
745 | 142k | } |
746 | 142k | } |
747 | | |
748 | 165k | for (j = 0; j < blocks_count; j++) { |
749 | 154k | int idom = blocks[j].idom, level = 0; |
750 | 154k | if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) { |
751 | 32 | continue; |
752 | 32 | } |
753 | 159k | while (idom >= 0) { |
754 | 148k | level++; |
755 | 148k | if (blocks[idom].level >= 0) { |
756 | 142k | level += blocks[idom].level; |
757 | 142k | break; |
758 | 142k | } else { |
759 | 5.59k | idom = blocks[idom].idom; |
760 | 5.59k | } |
761 | 148k | } |
762 | 154k | blocks[j].level = level; |
763 | 154k | } |
764 | | |
765 | 11.5k | free_alloca(postnum, use_heap); |
766 | 11.5k | } |
767 | | /* }}} */ |
768 | | |
769 | | static bool dominates(zend_basic_block *blocks, int a, int b) /* {{{ */ |
770 | 71.3k | { |
771 | 102k | while (blocks[b].level > blocks[a].level) { |
772 | 30.9k | b = blocks[b].idom; |
773 | 30.9k | } |
774 | 71.3k | return a == b; |
775 | 71.3k | } |
776 | | /* }}} */ |
777 | | |
778 | | ZEND_API void zend_cfg_identify_loops(const zend_op_array *op_array, zend_cfg *cfg) /* {{{ */ |
779 | 74.1k | { |
780 | 74.1k | int i, j, k, n; |
781 | 74.1k | int time; |
782 | 74.1k | zend_basic_block *blocks = cfg->blocks; |
783 | 74.1k | int *entry_times, *exit_times; |
784 | 74.1k | zend_worklist work; |
785 | 74.1k | int flag = ZEND_FUNC_NO_LOOPS; |
786 | 74.1k | int *sorted_blocks; |
787 | 74.1k | ALLOCA_FLAG(list_use_heap) |
788 | 74.1k | ALLOCA_FLAG(tree_use_heap) |
789 | | |
790 | 74.1k | if (cfg->blocks_count == 1) { |
791 | 62.5k | cfg->flags |= flag; |
792 | 62.5k | return; |
793 | 62.5k | } |
794 | | |
795 | 11.5k | ZEND_WORKLIST_ALLOCA(&work, cfg->blocks_count, list_use_heap); |
796 | | |
797 | | /* We don't materialize the DJ spanning tree explicitly, as we are only interested in ancestor |
798 | | * queries. These are implemented by checking entry/exit times of the DFS search. */ |
799 | 11.5k | entry_times = do_alloca(3 * sizeof(int) * cfg->blocks_count, tree_use_heap); |
800 | 11.5k | exit_times = entry_times + cfg->blocks_count; |
801 | 11.5k | sorted_blocks = exit_times + cfg->blocks_count; |
802 | 11.5k | memset(entry_times, -1, 2 * sizeof(int) * cfg->blocks_count); |
803 | | |
804 | 11.5k | zend_worklist_push(&work, 0); |
805 | 11.5k | time = 0; |
806 | 165k | while (zend_worklist_len(&work)) { |
807 | 296k | next: |
808 | 296k | i = zend_worklist_peek(&work); |
809 | 296k | if (entry_times[i] == -1) { |
810 | 154k | entry_times[i] = time++; |
811 | 154k | } |
812 | | /* Visit blocks immediately dominated by i. */ |
813 | 453k | for (j = blocks[i].children; j >= 0; j = blocks[j].next_child) { |
814 | 242k | if (zend_worklist_push(&work, j)) { |
815 | 85.3k | goto next; |
816 | 85.3k | } |
817 | 242k | } |
818 | | /* Visit join edges. */ |
819 | 422k | for (j = 0; j < blocks[i].successors_count; j++) { |
820 | 268k | int succ = blocks[i].successors[j]; |
821 | 268k | if (blocks[succ].idom == i) { |
822 | 139k | continue; |
823 | 139k | } else if (zend_worklist_push(&work, succ)) { |
824 | 57.1k | goto next; |
825 | 57.1k | } |
826 | 268k | } |
827 | 154k | exit_times[i] = time++; |
828 | 154k | zend_worklist_pop(&work); |
829 | 154k | } |
830 | | |
831 | | /* Sort blocks by level, which is the opposite order in which we want to process them */ |
832 | 11.5k | sorted_blocks[0] = 0; |
833 | 11.5k | j = 0; |
834 | 11.5k | n = 1; |
835 | 96.0k | while (j != n) { |
836 | 84.4k | i = j; |
837 | 84.4k | j = n; |
838 | 238k | for (; i < j; i++) { |
839 | 154k | int child; |
840 | 296k | for (child = blocks[sorted_blocks[i]].children; child >= 0; child = blocks[child].next_child) { |
841 | 142k | sorted_blocks[n++] = child; |
842 | 142k | } |
843 | 154k | } |
844 | 84.4k | } |
845 | | |
846 | | /* Identify loops. See Sreedhar et al, "Identifying Loops Using DJ Graphs". */ |
847 | 165k | while (n > 0) { |
848 | 154k | i = sorted_blocks[--n]; |
849 | | |
850 | 154k | if (blocks[i].predecessors_count < 2) { |
851 | | /* loop header has at least two input edges */ |
852 | 87.2k | continue; |
853 | 87.2k | } |
854 | | |
855 | 202k | for (j = 0; j < blocks[i].predecessors_count; j++) { |
856 | 135k | int pred = cfg->predecessors[blocks[i].predecessor_offset + j]; |
857 | | |
858 | | /* A join edge is one for which the predecessor does not |
859 | | immediately dominate the successor. */ |
860 | 135k | if (blocks[i].idom == pred) { |
861 | 63.9k | continue; |
862 | 63.9k | } |
863 | | |
864 | | /* In a loop back-edge (back-join edge), the successor dominates |
865 | | the predecessor. */ |
866 | 71.3k | if (dominates(blocks, i, pred)) { |
867 | 10.5k | blocks[i].flags |= ZEND_BB_LOOP_HEADER; |
868 | 10.5k | flag &= ~ZEND_FUNC_NO_LOOPS; |
869 | 10.5k | if (!zend_worklist_len(&work)) { |
870 | 9.75k | zend_bitset_clear(work.visited, zend_bitset_len(cfg->blocks_count)); |
871 | 9.75k | } |
872 | 10.5k | zend_worklist_push(&work, pred); |
873 | 60.8k | } else { |
874 | | /* Otherwise it's a cross-join edge. See if it's a branch |
875 | | to an ancestor on the DJ spanning tree. */ |
876 | 60.8k | if (entry_times[pred] > entry_times[i] && exit_times[pred] < exit_times[i]) { |
877 | 0 | blocks[i].flags |= ZEND_BB_IRREDUCIBLE_LOOP; |
878 | 0 | flag |= ZEND_FUNC_IRREDUCIBLE; |
879 | 0 | flag &= ~ZEND_FUNC_NO_LOOPS; |
880 | 0 | } |
881 | 60.8k | } |
882 | 71.3k | } |
883 | 118k | while (zend_worklist_len(&work)) { |
884 | 52.1k | j = zend_worklist_pop(&work); |
885 | 54.9k | while (blocks[j].loop_header >= 0) { |
886 | 2.79k | j = blocks[j].loop_header; |
887 | 2.79k | } |
888 | 52.1k | if (j != i) { |
889 | 40.9k | if (blocks[j].idom < 0 && j != 0) { |
890 | | /* Ignore blocks that are unreachable or only abnormally reachable. */ |
891 | 0 | continue; |
892 | 0 | } |
893 | 40.9k | blocks[j].loop_header = i; |
894 | 97.7k | for (k = 0; k < blocks[j].predecessors_count; k++) { |
895 | 56.8k | zend_worklist_push(&work, cfg->predecessors[blocks[j].predecessor_offset + k]); |
896 | 56.8k | } |
897 | 40.9k | } |
898 | 52.1k | } |
899 | 66.8k | } |
900 | | |
901 | 11.5k | free_alloca(entry_times, tree_use_heap); |
902 | 11.5k | ZEND_WORKLIST_FREE_ALLOCA(&work, list_use_heap); |
903 | | |
904 | 11.5k | cfg->flags |= flag; |
905 | 11.5k | } |
906 | | /* }}} */ |