xref: /PHP-8.1/Zend/Optimizer/zend_cfg.c (revision f455894b)
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