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