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