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