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