xref: /PHP-8.0/ext/opcache/Optimizer/zend_ssa.c (revision 6f42c073)
1 /*
2    +----------------------------------------------------------------------+
3    | Zend Engine, SSA - Static Single Assignment Form                     |
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    |          Nikita Popov <nikic@php.net>                                |
17    +----------------------------------------------------------------------+
18 */
19 
20 #include "php.h"
21 #include "zend_compile.h"
22 #include "zend_dfg.h"
23 #include "zend_ssa.h"
24 #include "zend_dump.h"
25 #include "zend_inference.h"
26 #include "Optimizer/zend_optimizer_internal.h"
27 
dominates(const zend_basic_block * blocks,int a,int b)28 static zend_bool dominates(const zend_basic_block *blocks, int a, int b) {
29 	while (blocks[b].level > blocks[a].level) {
30 		b = blocks[b].idom;
31 	}
32 	return a == b;
33 }
34 
will_rejoin(const zend_cfg * cfg,const zend_dfg * dfg,const zend_basic_block * block,int other_successor,int exclude,int var)35 static zend_bool will_rejoin(
36 		const zend_cfg *cfg, const zend_dfg *dfg, const zend_basic_block *block,
37 		int other_successor, int exclude, int var) {
38 	int i;
39 	for (i = 0; i < block->predecessors_count; i++) {
40 		int predecessor = cfg->predecessors[block->predecessor_offset + i];
41 		if (predecessor == exclude) {
42 			continue;
43 		}
44 
45 		/* The variable is changed in this predecessor,
46 		 * so we will not rejoin with the original value. */
47 		// TODO: This should not be limited to the direct predecessor block.
48 		if (DFG_ISSET(dfg->def, dfg->size, predecessor, var)) {
49 			continue;
50 		}
51 
52 		/* The other successor dominates this predecessor,
53 		 * so we will get the original value from it. */
54 		if (dominates(cfg->blocks, other_successor, predecessor)) {
55 			return 1;
56 		}
57 	}
58 	return 0;
59 }
60 
needs_pi(const zend_op_array * op_array,zend_dfg * dfg,zend_ssa * ssa,int from,int to,int var)61 static zend_bool needs_pi(const zend_op_array *op_array, zend_dfg *dfg, zend_ssa *ssa, int from, int to, int var) /* {{{ */
62 {
63 	zend_basic_block *from_block, *to_block;
64 	int other_successor;
65 
66 	if (!DFG_ISSET(dfg->in, dfg->size, to, var)) {
67 		/* Variable is not live, certainly won't benefit from pi */
68 		return 0;
69 	}
70 
71 	/* Make sure that both successors of the from block aren't the same. Pi nodes are associated
72 	 * with predecessor blocks, so we can't distinguish which edge the pi belongs to. */
73 	from_block = &ssa->cfg.blocks[from];
74 	ZEND_ASSERT(from_block->successors_count == 2);
75 	if (from_block->successors[0] == from_block->successors[1]) {
76 		return 0;
77 	}
78 
79 	to_block = &ssa->cfg.blocks[to];
80 	if (to_block->predecessors_count == 1) {
81 		/* Always place pi if one predecessor (an if branch) */
82 		return 1;
83 	}
84 
85 	/* Check whether we will rejoin with the original value coming from the other successor,
86 	 * in which case the pi node will not have an effect. */
87 	other_successor = from_block->successors[0] == to
88 		? from_block->successors[1] : from_block->successors[0];
89 	return !will_rejoin(&ssa->cfg, dfg, to_block, other_successor, from, var);
90 }
91 /* }}} */
92 
add_pi(zend_arena ** arena,const zend_op_array * op_array,zend_dfg * dfg,zend_ssa * ssa,int from,int to,int var)93 static zend_ssa_phi *add_pi(
94 		zend_arena **arena, const zend_op_array *op_array, zend_dfg *dfg, zend_ssa *ssa,
95 		int from, int to, int var) /* {{{ */
96 {
97 	zend_ssa_phi *phi;
98 	if (!needs_pi(op_array, dfg, ssa, from, to, var)) {
99 		return NULL;
100 	}
101 
102 	phi = zend_arena_calloc(arena, 1,
103 		ZEND_MM_ALIGNED_SIZE(sizeof(zend_ssa_phi)) +
104 		ZEND_MM_ALIGNED_SIZE(sizeof(int) * ssa->cfg.blocks[to].predecessors_count) +
105 		sizeof(void*) * ssa->cfg.blocks[to].predecessors_count);
106 	phi->sources = (int*)(((char*)phi) + ZEND_MM_ALIGNED_SIZE(sizeof(zend_ssa_phi)));
107 	memset(phi->sources, 0xff, sizeof(int) * ssa->cfg.blocks[to].predecessors_count);
108 	phi->use_chains = (zend_ssa_phi**)(((char*)phi->sources) + ZEND_MM_ALIGNED_SIZE(sizeof(int) * ssa->cfg.blocks[to].predecessors_count));
109 
110 	phi->pi = from;
111 	phi->var = var;
112 	phi->ssa_var = -1;
113 	phi->next = ssa->blocks[to].phis;
114 	ssa->blocks[to].phis = phi;
115 
116 	/* Block "to" now defines "var" via the pi statement, so add it to the "def" set. Note that
117 	 * this is not entirely accurate, because the pi is actually placed along the edge from->to.
118 	 * If there is a back-edge to "to" this may result in non-minimal SSA form. */
119 	DFG_SET(dfg->def, dfg->size, to, var);
120 
121 	/* If there are multiple predecessors in the target block, we need to place a phi there.
122 	 * However this can (generally) not be expressed in terms of dominance frontiers, so place it
123 	 * explicitly. dfg->use here really is dfg->phi, we're reusing the set. */
124 	if (ssa->cfg.blocks[to].predecessors_count > 1) {
125 		DFG_SET(dfg->use, dfg->size, to, var);
126 	}
127 
128 	return phi;
129 }
130 /* }}} */
131 
pi_range(zend_ssa_phi * phi,int min_var,int max_var,zend_long min,zend_long max,char underflow,char overflow,char negative)132 static void pi_range(
133 		zend_ssa_phi *phi, int min_var, int max_var, zend_long min, zend_long max,
134 		char underflow, char overflow, char negative) /* {{{ */
135 {
136 	zend_ssa_range_constraint *constraint = &phi->constraint.range;
137 	constraint->min_var = min_var;
138 	constraint->max_var = max_var;
139 	constraint->min_ssa_var = -1;
140 	constraint->max_ssa_var = -1;
141 	constraint->range.min = min;
142 	constraint->range.max = max;
143 	constraint->range.underflow = underflow;
144 	constraint->range.overflow = overflow;
145 	constraint->negative = negative ? NEG_INIT : NEG_NONE;
146 	phi->has_range_constraint = 1;
147 }
148 /* }}} */
149 
pi_range_equals(zend_ssa_phi * phi,int var,zend_long val)150 static inline void pi_range_equals(zend_ssa_phi *phi, int var, zend_long val) {
151 	pi_range(phi, var, var, val, val, 0, 0, 0);
152 }
pi_range_not_equals(zend_ssa_phi * phi,int var,zend_long val)153 static inline void pi_range_not_equals(zend_ssa_phi *phi, int var, zend_long val) {
154 	pi_range(phi, var, var, val, val, 0, 0, 1);
155 }
pi_range_min(zend_ssa_phi * phi,int var,zend_long val)156 static inline void pi_range_min(zend_ssa_phi *phi, int var, zend_long val) {
157 	pi_range(phi, var, -1, val, ZEND_LONG_MAX, 0, 1, 0);
158 }
pi_range_max(zend_ssa_phi * phi,int var,zend_long val)159 static inline void pi_range_max(zend_ssa_phi *phi, int var, zend_long val) {
160 	pi_range(phi, -1, var, ZEND_LONG_MIN, val, 1, 0, 0);
161 }
162 
pi_type_mask(zend_ssa_phi * phi,uint32_t type_mask)163 static void pi_type_mask(zend_ssa_phi *phi, uint32_t type_mask) {
164 	phi->has_range_constraint = 0;
165 	phi->constraint.type.ce = NULL;
166 	phi->constraint.type.type_mask = MAY_BE_REF|MAY_BE_RC1|MAY_BE_RCN;
167 	phi->constraint.type.type_mask |= type_mask;
168 	if (type_mask & MAY_BE_NULL) {
169 		phi->constraint.type.type_mask |= MAY_BE_UNDEF;
170 	}
171 }
pi_not_type_mask(zend_ssa_phi * phi,uint32_t type_mask)172 static inline void pi_not_type_mask(zend_ssa_phi *phi, uint32_t type_mask) {
173 	uint32_t relevant = MAY_BE_ANY|MAY_BE_ARRAY_KEY_ANY|MAY_BE_ARRAY_OF_ANY|MAY_BE_ARRAY_OF_REF;
174 	pi_type_mask(phi, ~type_mask & relevant);
175 }
mask_for_type_check(uint32_t type)176 static inline uint32_t mask_for_type_check(uint32_t type) {
177 	if (type & MAY_BE_ARRAY) {
178 		return type | (MAY_BE_ARRAY_KEY_ANY|MAY_BE_ARRAY_OF_ANY|MAY_BE_ARRAY_OF_REF);
179 	} else {
180 		return type;
181 	}
182 }
183 
184 /* We can interpret $a + 5 == 0 as $a = 0 - 5, i.e. shift the adjustment to the other operand.
185  * This negated adjustment is what is written into the "adjustment" parameter. */
find_adjusted_tmp_var(const zend_op_array * op_array,uint32_t build_flags,zend_op * opline,uint32_t var_num,zend_long * adjustment)186 static int find_adjusted_tmp_var(const zend_op_array *op_array, uint32_t build_flags, zend_op *opline, uint32_t var_num, zend_long *adjustment) /* {{{ */
187 {
188 	zend_op *op = opline;
189 	zval *zv;
190 
191 	while (op != op_array->opcodes) {
192 		op--;
193 		if (op->result_type != IS_TMP_VAR || op->result.var != var_num) {
194 			continue;
195 		}
196 
197 		if (op->opcode == ZEND_POST_DEC) {
198 			if (op->op1_type == IS_CV) {
199 				*adjustment = -1;
200 				return EX_VAR_TO_NUM(op->op1.var);
201 			}
202 		} else if (op->opcode == ZEND_POST_INC) {
203 			if (op->op1_type == IS_CV) {
204 				*adjustment = 1;
205 				return EX_VAR_TO_NUM(op->op1.var);
206 			}
207 		} else if (op->opcode == ZEND_ADD) {
208 			if (op->op1_type == IS_CV && op->op2_type == IS_CONST) {
209 				zv = CRT_CONSTANT_EX(op_array, op, op->op2);
210 				if (Z_TYPE_P(zv) == IS_LONG
211 				 && Z_LVAL_P(zv) != ZEND_LONG_MIN) {
212 					*adjustment = -Z_LVAL_P(zv);
213 					return EX_VAR_TO_NUM(op->op1.var);
214 				}
215 			} else if (op->op2_type == IS_CV && op->op1_type == IS_CONST) {
216 				zv = CRT_CONSTANT_EX(op_array, op, op->op1);
217 				if (Z_TYPE_P(zv) == IS_LONG
218 				 && Z_LVAL_P(zv) != ZEND_LONG_MIN) {
219 					*adjustment = -Z_LVAL_P(zv);
220 					return EX_VAR_TO_NUM(op->op2.var);
221 				}
222 			}
223 		} else if (op->opcode == ZEND_SUB) {
224 			if (op->op1_type == IS_CV && op->op2_type == IS_CONST) {
225 				zv = CRT_CONSTANT_EX(op_array, op, op->op2);
226 				if (Z_TYPE_P(zv) == IS_LONG) {
227 					*adjustment = Z_LVAL_P(zv);
228 					return EX_VAR_TO_NUM(op->op1.var);
229 				}
230 			}
231 		}
232 		break;
233 	}
234 	return -1;
235 }
236 /* }}} */
237 
238 /* e-SSA construction: Pi placement (Pi is actually a Phi with single
239  * source and constraint).
240  * Order of Phis is important, Pis must be placed before Phis
241  */
place_essa_pis(zend_arena ** arena,const zend_script * script,const zend_op_array * op_array,uint32_t build_flags,zend_ssa * ssa,zend_dfg * dfg)242 static void place_essa_pis(
243 		zend_arena **arena, const zend_script *script, const zend_op_array *op_array,
244 		uint32_t build_flags, zend_ssa *ssa, zend_dfg *dfg) /* {{{ */ {
245 	zend_basic_block *blocks = ssa->cfg.blocks;
246 	int j, blocks_count = ssa->cfg.blocks_count;
247 	for (j = 0; j < blocks_count; j++) {
248 		zend_ssa_phi *pi;
249 		zend_op *opline = op_array->opcodes + blocks[j].start + blocks[j].len - 1;
250 		int bt; /* successor block number if a condition is true */
251 		int bf; /* successor block number if a condition is false */
252 
253 		if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0 || blocks[j].len == 0) {
254 			continue;
255 		}
256 		/* the last instruction of basic block is conditional branch,
257 		 * based on comparison of CV(s)
258 		 */
259 		switch (opline->opcode) {
260 			case ZEND_JMPZ:
261 			case ZEND_JMPZNZ:
262 				bf = blocks[j].successors[0];
263 				bt = blocks[j].successors[1];
264 				break;
265 			case ZEND_JMPNZ:
266 				bt = blocks[j].successors[0];
267 				bf = blocks[j].successors[1];
268 				break;
269 			case ZEND_COALESCE:
270 				if (opline->op1_type == IS_CV) {
271 					int var = EX_VAR_TO_NUM(opline->op1.var);
272 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, blocks[j].successors[0], var))) {
273 						pi_not_type_mask(pi, MAY_BE_NULL);
274 					}
275 				}
276 				continue;
277 			case ZEND_JMP_NULL:
278 				if (opline->op1_type == IS_CV) {
279 					int var = EX_VAR_TO_NUM(opline->op1.var);
280 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, blocks[j].successors[1], var))) {
281 						pi_not_type_mask(pi, MAY_BE_NULL);
282 					}
283 				}
284 				continue;
285 			default:
286 				continue;
287 		}
288 
289 		/* The following patterns all inspect the opline directly before the JMPZ opcode.
290 		 * Make sure that it is part of the same block, otherwise it might not be a dominating
291 		 * assignment. */
292 		if (blocks[j].len == 1) {
293 			continue;
294 		}
295 
296 		if (opline->op1_type == IS_TMP_VAR &&
297 		    ((opline-1)->opcode == ZEND_IS_EQUAL ||
298 		     (opline-1)->opcode == ZEND_IS_NOT_EQUAL ||
299 		     (opline-1)->opcode == ZEND_IS_SMALLER ||
300 		     (opline-1)->opcode == ZEND_IS_SMALLER_OR_EQUAL) &&
301 		    opline->op1.var == (opline-1)->result.var) {
302 			int  var1 = -1;
303 			int  var2 = -1;
304 			zend_long val1 = 0;
305 			zend_long val2 = 0;
306 //			long val = 0;
307 
308 			if ((opline-1)->op1_type == IS_CV) {
309 				var1 = EX_VAR_TO_NUM((opline-1)->op1.var);
310 			} else if ((opline-1)->op1_type == IS_TMP_VAR) {
311 				var1 = find_adjusted_tmp_var(
312 					op_array, build_flags, opline, (opline-1)->op1.var, &val2);
313 			}
314 
315 			if ((opline-1)->op2_type == IS_CV) {
316 				var2 = EX_VAR_TO_NUM((opline-1)->op2.var);
317 			} else if ((opline-1)->op2_type == IS_TMP_VAR) {
318 				var2 = find_adjusted_tmp_var(
319 					op_array, build_flags, opline, (opline-1)->op2.var, &val1);
320 			}
321 
322 			if (var1 >= 0 && var2 >= 0) {
323 				if (!zend_sub_will_overflow(val1, val2) && !zend_sub_will_overflow(val2, val1)) {
324 					zend_long tmp = val1;
325 					val1 -= val2;
326 					val2 -= tmp;
327 				} else {
328 					var1 = -1;
329 					var2 = -1;
330 				}
331 			} else if (var1 >= 0 && var2 < 0) {
332 				zend_long add_val2 = 0;
333 				if ((opline-1)->op2_type == IS_CONST) {
334 					zval *zv = CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op2);
335 
336 					if (Z_TYPE_P(zv) == IS_LONG) {
337 						add_val2 = Z_LVAL_P(zv);
338 					} else {
339 						var1 = -1;
340 					}
341 				} else {
342 					var1 = -1;
343 				}
344 				if (!zend_add_will_overflow(val2, add_val2)) {
345 					val2 += add_val2;
346 				} else {
347 					var1 = -1;
348 				}
349 			} else if (var1 < 0 && var2 >= 0) {
350 				zend_long add_val1 = 0;
351 				if ((opline-1)->op1_type == IS_CONST) {
352 					zval *zv = CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op1);
353 					if (Z_TYPE_P(zv) == IS_LONG) {
354 						add_val1 = Z_LVAL_P(CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op1));
355 					} else {
356 						var2 = -1;
357 					}
358 				} else {
359 					var2 = -1;
360 				}
361 				if (!zend_add_will_overflow(val1, add_val1)) {
362 					val1 += add_val1;
363 				} else {
364 					var2 = -1;
365 				}
366 			}
367 
368 			if (var1 >= 0) {
369 				if ((opline-1)->opcode == ZEND_IS_EQUAL) {
370 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var1))) {
371 						pi_range_equals(pi, var2, val2);
372 					}
373 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var1))) {
374 						pi_range_not_equals(pi, var2, val2);
375 					}
376 				} else if ((opline-1)->opcode == ZEND_IS_NOT_EQUAL) {
377 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var1))) {
378 						pi_range_equals(pi, var2, val2);
379 					}
380 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var1))) {
381 						pi_range_not_equals(pi, var2, val2);
382 					}
383 				} else if ((opline-1)->opcode == ZEND_IS_SMALLER) {
384 					if (val2 > ZEND_LONG_MIN) {
385 						if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var1))) {
386 							pi_range_max(pi, var2, val2-1);
387 						}
388 					}
389 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var1))) {
390 						pi_range_min(pi, var2, val2);
391 					}
392 				} else if ((opline-1)->opcode == ZEND_IS_SMALLER_OR_EQUAL) {
393 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var1))) {
394 						pi_range_max(pi, var2, val2);
395 					}
396 					if (val2 < ZEND_LONG_MAX) {
397 						if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var1))) {
398 							pi_range_min(pi, var2, val2+1);
399 						}
400 					}
401 				}
402 			}
403 			if (var2 >= 0) {
404 				if((opline-1)->opcode == ZEND_IS_EQUAL) {
405 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var2))) {
406 						pi_range_equals(pi, var1, val1);
407 					}
408 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var2))) {
409 						pi_range_not_equals(pi, var1, val1);
410 					}
411 				} else if ((opline-1)->opcode == ZEND_IS_NOT_EQUAL) {
412 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var2))) {
413 						pi_range_equals(pi, var1, val1);
414 					}
415 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var2))) {
416 						pi_range_not_equals(pi, var1, val1);
417 					}
418 				} else if ((opline-1)->opcode == ZEND_IS_SMALLER) {
419 					if (val1 < ZEND_LONG_MAX) {
420 						if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var2))) {
421 							pi_range_min(pi, var1, val1+1);
422 						}
423 					}
424 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var2))) {
425 						pi_range_max(pi, var1, val1);
426 					}
427 				} else if ((opline-1)->opcode == ZEND_IS_SMALLER_OR_EQUAL) {
428 					if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var2))) {
429 						pi_range_min(pi, var1, val1);
430 					}
431 					if (val1 > ZEND_LONG_MIN) {
432 						if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var2))) {
433 							pi_range_max(pi, var1, val1-1);
434 						}
435 					}
436 				}
437 			}
438 		} else if (opline->op1_type == IS_TMP_VAR &&
439 		           ((opline-1)->opcode == ZEND_POST_INC ||
440 		            (opline-1)->opcode == ZEND_POST_DEC) &&
441 		           opline->op1.var == (opline-1)->result.var &&
442 		           (opline-1)->op1_type == IS_CV) {
443 			int var = EX_VAR_TO_NUM((opline-1)->op1.var);
444 
445 			if ((opline-1)->opcode == ZEND_POST_DEC) {
446 				if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
447 					pi_range_equals(pi, -1, -1);
448 				}
449 				if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
450 					pi_range_not_equals(pi, -1, -1);
451 				}
452 			} else if ((opline-1)->opcode == ZEND_POST_INC) {
453 				if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
454 					pi_range_equals(pi, -1, 1);
455 				}
456 				if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
457 					pi_range_not_equals(pi, -1, 1);
458 				}
459 			}
460 		} else if (opline->op1_type == IS_TMP_VAR &&
461 		           ((opline-1)->opcode == ZEND_PRE_INC ||
462 		            (opline-1)->opcode == ZEND_PRE_DEC) &&
463 		           opline->op1.var == (opline-1)->result.var &&
464 		           (opline-1)->op1_type == IS_CV) {
465 			int var = EX_VAR_TO_NUM((opline-1)->op1.var);
466 
467 			if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
468 				pi_range_equals(pi, -1, 0);
469 			}
470 			/* speculative */
471 			if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
472 				pi_range_not_equals(pi, -1, 0);
473 			}
474 		} else if (opline->op1_type == IS_TMP_VAR && (opline-1)->opcode == ZEND_TYPE_CHECK &&
475 				   opline->op1.var == (opline-1)->result.var && (opline-1)->op1_type == IS_CV) {
476 			int var = EX_VAR_TO_NUM((opline-1)->op1.var);
477 			uint32_t type = (opline-1)->extended_value;
478 			if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
479 				pi_type_mask(pi, mask_for_type_check(type));
480 			}
481 			if (type != MAY_BE_RESOURCE) {
482 				/* is_resource() may return false for closed resources */
483 				if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
484 					pi_not_type_mask(pi, mask_for_type_check(type));
485 				}
486 			}
487 		} else if (opline->op1_type == IS_TMP_VAR &&
488 				   ((opline-1)->opcode == ZEND_IS_IDENTICAL
489 					|| (opline-1)->opcode == ZEND_IS_NOT_IDENTICAL) &&
490 				   opline->op1.var == (opline-1)->result.var) {
491 			int var;
492 			zval *val;
493 			uint32_t type_mask;
494 			if ((opline-1)->op1_type == IS_CV && (opline-1)->op2_type == IS_CONST) {
495 				var = EX_VAR_TO_NUM((opline-1)->op1.var);
496 				val = CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op2);
497 			} else if ((opline-1)->op1_type == IS_CONST && (opline-1)->op2_type == IS_CV) {
498 				var = EX_VAR_TO_NUM((opline-1)->op2.var);
499 				val = CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op1);
500 			} else {
501 				continue;
502 			}
503 
504 			/* We're interested in === null/true/false comparisons here, because they eliminate
505 			 * a type in the false-branch. Other === VAL comparisons are unlikely to be useful. */
506 			if (Z_TYPE_P(val) != IS_NULL && Z_TYPE_P(val) != IS_TRUE && Z_TYPE_P(val) != IS_FALSE) {
507 				continue;
508 			}
509 
510 			type_mask = _const_op_type(val);
511 			if ((opline-1)->opcode == ZEND_IS_IDENTICAL) {
512 				if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
513 					pi_type_mask(pi, type_mask);
514 				}
515 				if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
516 					pi_not_type_mask(pi, type_mask);
517 				}
518 			} else {
519 				if ((pi = add_pi(arena, op_array, dfg, ssa, j, bf, var))) {
520 					pi_type_mask(pi, type_mask);
521 				}
522 				if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
523 					pi_not_type_mask(pi, type_mask);
524 				}
525 			}
526 		} else if (opline->op1_type == IS_TMP_VAR && (opline-1)->opcode == ZEND_INSTANCEOF &&
527 				   opline->op1.var == (opline-1)->result.var && (opline-1)->op1_type == IS_CV &&
528 				   (opline-1)->op2_type == IS_CONST) {
529 			int var = EX_VAR_TO_NUM((opline-1)->op1.var);
530 			zend_string *lcname = Z_STR_P(CRT_CONSTANT_EX(op_array, (opline-1), (opline-1)->op2) + 1);
531 			zend_class_entry *ce = script ? zend_hash_find_ptr(&script->class_table, lcname) : NULL;
532 			if (!ce) {
533 				ce = zend_hash_find_ptr(CG(class_table), lcname);
534 				if (!ce || ce->type != ZEND_INTERNAL_CLASS) {
535 					continue;
536 				}
537 			}
538 
539 			if ((pi = add_pi(arena, op_array, dfg, ssa, j, bt, var))) {
540 				pi_type_mask(pi, MAY_BE_OBJECT);
541 				pi->constraint.type.ce = ce;
542 			}
543 		}
544 	}
545 }
546 /* }}} */
547 
_zend_ssa_rename_op(const zend_op_array * op_array,const zend_op * opline,uint32_t k,uint32_t build_flags,int ssa_vars_count,zend_ssa_op * ssa_ops,int * var)548 static zend_always_inline int _zend_ssa_rename_op(const zend_op_array *op_array, const zend_op *opline, uint32_t k, uint32_t build_flags, int ssa_vars_count, zend_ssa_op *ssa_ops, int *var) /* {{{ */
549 {
550 	const zend_op *next;
551 
552 	if (opline->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
553 		ssa_ops[k].op1_use = var[EX_VAR_TO_NUM(opline->op1.var)];
554 		//USE_SSA_VAR(op_array->last_var + opline->op1.var)
555 	}
556 	if (opline->op2_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
557 		ssa_ops[k].op2_use = var[EX_VAR_TO_NUM(opline->op2.var)];
558 		//USE_SSA_VAR(op_array->last_var + opline->op2.var)
559 	}
560 	if ((build_flags & ZEND_SSA_USE_CV_RESULTS)
561 	 && opline->result_type == IS_CV
562 	 && opline->opcode != ZEND_RECV) {
563 		ssa_ops[k].result_use = var[EX_VAR_TO_NUM(opline->result.var)];
564 		//USE_SSA_VAR(op_array->last_var + opline->result.var)
565 	}
566 
567 	switch (opline->opcode) {
568 		case ZEND_ASSIGN:
569 			if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op2_type == IS_CV) {
570 				ssa_ops[k].op2_def = ssa_vars_count;
571 				var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count;
572 				ssa_vars_count++;
573 				//NEW_SSA_VAR(opline->op2.var)
574 			}
575 			if (opline->op1_type == IS_CV) {
576 add_op1_def:
577 				ssa_ops[k].op1_def = ssa_vars_count;
578 				var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
579 				ssa_vars_count++;
580 				//NEW_SSA_VAR(opline->op1.var)
581 			}
582 			break;
583 		case ZEND_ASSIGN_REF:
584 			if (opline->op2_type == IS_CV) {
585 				ssa_ops[k].op2_def = ssa_vars_count;
586 				var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count;
587 				ssa_vars_count++;
588 				//NEW_SSA_VAR(opline->op2.var)
589 			}
590 			if (opline->op1_type == IS_CV) {
591 				goto add_op1_def;
592 			}
593 			break;
594 		case ZEND_ASSIGN_DIM:
595 		case ZEND_ASSIGN_OBJ:
596 			if (opline->op1_type == IS_CV) {
597 				ssa_ops[k].op1_def = ssa_vars_count;
598 				var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
599 				ssa_vars_count++;
600 				//NEW_SSA_VAR(opline->op1.var)
601 			}
602 			next = opline + 1;
603 			if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
604 				ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
605 				//USE_SSA_VAR(op_array->last_var + next->op1.var);
606 				if (build_flags & ZEND_SSA_RC_INFERENCE && next->op1_type == IS_CV) {
607 					ssa_ops[k + 1].op1_def = ssa_vars_count;
608 					var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count;
609 					ssa_vars_count++;
610 					//NEW_SSA_VAR(next->op1.var)
611 				}
612 			}
613 			break;
614 		case ZEND_ASSIGN_OBJ_REF:
615 			if (opline->op1_type == IS_CV) {
616 				ssa_ops[k].op1_def = ssa_vars_count;
617 				var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
618 				ssa_vars_count++;
619 				//NEW_SSA_VAR(opline->op1.var)
620 			}
621 			next = opline + 1;
622 			if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
623 				ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
624 				//USE_SSA_VAR(op_array->last_var + next->op1.var);
625 				if (next->op1_type == IS_CV) {
626 					ssa_ops[k + 1].op1_def = ssa_vars_count;
627 					var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count;
628 					ssa_vars_count++;
629 					//NEW_SSA_VAR(next->op1.var)
630 				}
631 			}
632 			break;
633 		case ZEND_ASSIGN_STATIC_PROP:
634 			next = opline + 1;
635 			if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
636 				ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
637 				//USE_SSA_VAR(op_array->last_var + next->op1.var);
638 				if ((build_flags & ZEND_SSA_RC_INFERENCE) && next->op1_type == IS_CV) {
639 					ssa_ops[k + 1].op1_def = ssa_vars_count;
640 					var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count;
641 					ssa_vars_count++;
642 					//NEW_SSA_VAR(next->op1.var)
643 				}
644 			}
645 			break;
646 		case ZEND_ASSIGN_STATIC_PROP_REF:
647 			next = opline + 1;
648 			if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
649 				ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
650 				//USE_SSA_VAR(op_array->last_var + next->op1.var);
651 				if (next->op1_type == IS_CV) {
652 					ssa_ops[k + 1].op1_def = ssa_vars_count;
653 					var[EX_VAR_TO_NUM(next->op1.var)] = ssa_vars_count;
654 					ssa_vars_count++;
655 					//NEW_SSA_VAR(next->op1.var)
656 				}
657 			}
658 			break;
659 		case ZEND_ASSIGN_STATIC_PROP_OP:
660 			next = opline + 1;
661 			if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
662 				ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
663 				//USE_SSA_VAR(op_array->last_var + next->op1.var);
664 			}
665 			break;
666 		case ZEND_ASSIGN_DIM_OP:
667 		case ZEND_ASSIGN_OBJ_OP:
668 			if (opline->op1_type == IS_CV) {
669 				ssa_ops[k].op1_def = ssa_vars_count;
670 				var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
671 				ssa_vars_count++;
672 				//NEW_SSA_VAR(opline->op1.var)
673 			}
674 			next = opline + 1;
675 			if (next->op1_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
676 				ssa_ops[k + 1].op1_use = var[EX_VAR_TO_NUM(next->op1.var)];
677 				//USE_SSA_VAR(op_array->last_var + next->op1.var);
678 			}
679 			break;
680 		case ZEND_ASSIGN_OP:
681 		case ZEND_PRE_INC:
682 		case ZEND_PRE_DEC:
683 		case ZEND_POST_INC:
684 		case ZEND_POST_DEC:
685 		case ZEND_BIND_GLOBAL:
686 		case ZEND_BIND_STATIC:
687 		case ZEND_SEND_VAR_NO_REF:
688 		case ZEND_SEND_VAR_NO_REF_EX:
689 		case ZEND_SEND_VAR_EX:
690 		case ZEND_SEND_FUNC_ARG:
691 		case ZEND_SEND_REF:
692 		case ZEND_SEND_UNPACK:
693 		case ZEND_FE_RESET_RW:
694 		case ZEND_MAKE_REF:
695 		case ZEND_PRE_INC_OBJ:
696 		case ZEND_PRE_DEC_OBJ:
697 		case ZEND_POST_INC_OBJ:
698 		case ZEND_POST_DEC_OBJ:
699 		case ZEND_UNSET_DIM:
700 		case ZEND_UNSET_OBJ:
701 		case ZEND_FETCH_DIM_W:
702 		case ZEND_FETCH_DIM_RW:
703 		case ZEND_FETCH_DIM_FUNC_ARG:
704 		case ZEND_FETCH_DIM_UNSET:
705 		case ZEND_FETCH_LIST_W:
706 			if (opline->op1_type == IS_CV) {
707 				goto add_op1_def;
708 			}
709 			break;
710 		case ZEND_SEND_VAR:
711 		case ZEND_CAST:
712 		case ZEND_QM_ASSIGN:
713 		case ZEND_JMP_SET:
714 		case ZEND_COALESCE:
715 		case ZEND_FE_RESET_R:
716 			if ((build_flags & ZEND_SSA_RC_INFERENCE) && opline->op1_type == IS_CV) {
717 				goto add_op1_def;
718 			}
719 			break;
720 		case ZEND_ADD_ARRAY_UNPACK:
721 			ssa_ops[k].result_use = var[EX_VAR_TO_NUM(opline->result.var)];
722 			break;
723 		case ZEND_ADD_ARRAY_ELEMENT:
724 			ssa_ops[k].result_use = var[EX_VAR_TO_NUM(opline->result.var)];
725 			/* break missing intentionally */
726 		case ZEND_INIT_ARRAY:
727 			if (((build_flags & ZEND_SSA_RC_INFERENCE)
728 						|| (opline->extended_value & ZEND_ARRAY_ELEMENT_REF))
729 					&& opline->op1_type == IS_CV) {
730 				goto add_op1_def;
731 			}
732 			break;
733 		case ZEND_YIELD:
734 			if (opline->op1_type == IS_CV
735 					&& ((op_array->fn_flags & ZEND_ACC_RETURN_REFERENCE)
736 						|| (build_flags & ZEND_SSA_RC_INFERENCE))) {
737 				goto add_op1_def;
738 			}
739 			break;
740 		case ZEND_UNSET_CV:
741 			goto add_op1_def;
742 		case ZEND_VERIFY_RETURN_TYPE:
743 			if (opline->op1_type & (IS_TMP_VAR|IS_VAR|IS_CV)) {
744 				goto add_op1_def;
745 			}
746 			break;
747 		case ZEND_FE_FETCH_R:
748 		case ZEND_FE_FETCH_RW:
749 			if (opline->op2_type != IS_CV) {
750 				ssa_ops[k].op2_use = -1; /* not used */
751 			}
752 			ssa_ops[k].op2_def = ssa_vars_count;
753 			var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count;
754 			ssa_vars_count++;
755 			//NEW_SSA_VAR(opline->op2.var)
756 			break;
757 		case ZEND_BIND_LEXICAL:
758 			if ((opline->extended_value & ZEND_BIND_REF) || (build_flags & ZEND_SSA_RC_INFERENCE)) {
759 				ssa_ops[k].op2_def = ssa_vars_count;
760 				var[EX_VAR_TO_NUM(opline->op2.var)] = ssa_vars_count;
761 				ssa_vars_count++;
762 				//NEW_SSA_VAR(opline->op2.var)
763 			}
764 			break;
765 		case ZEND_COPY_TMP:
766 			if (build_flags & ZEND_SSA_RC_INFERENCE) {
767 				ssa_ops[k].op1_def = ssa_vars_count;
768 				var[EX_VAR_TO_NUM(opline->op1.var)] = ssa_vars_count;
769 				ssa_vars_count++;
770 				//NEW_SSA_VAR(opline->op1.var)
771 			}
772 			break;
773 		default:
774 			break;
775 	}
776 
777 	if (opline->result_type & (IS_CV|IS_VAR|IS_TMP_VAR)) {
778 		ssa_ops[k].result_def = ssa_vars_count;
779 		var[EX_VAR_TO_NUM(opline->result.var)] = ssa_vars_count;
780 		ssa_vars_count++;
781 		//NEW_SSA_VAR(op_array->last_var + opline->result.var)
782 	}
783 
784 	return ssa_vars_count;
785 }
786 /* }}} */
787 
zend_ssa_rename_op(const zend_op_array * op_array,const zend_op * opline,uint32_t k,uint32_t build_flags,int ssa_vars_count,zend_ssa_op * ssa_ops,int * var)788 int zend_ssa_rename_op(const zend_op_array *op_array, const zend_op *opline, uint32_t k, uint32_t build_flags, int ssa_vars_count, zend_ssa_op *ssa_ops, int *var) /* {{{ */
789 {
790 	return _zend_ssa_rename_op(op_array, opline, k, build_flags, ssa_vars_count, ssa_ops, var);
791 }
792 /* }}} */
793 
zend_ssa_rename(const zend_op_array * op_array,uint32_t build_flags,zend_ssa * ssa,int * var,int n)794 static int zend_ssa_rename(const zend_op_array *op_array, uint32_t build_flags, zend_ssa *ssa, int *var, int n) /* {{{ */
795 {
796 	zend_basic_block *blocks = ssa->cfg.blocks;
797 	zend_ssa_block *ssa_blocks = ssa->blocks;
798 	zend_ssa_op *ssa_ops = ssa->ops;
799 	int ssa_vars_count = ssa->vars_count;
800 	int i, j;
801 	zend_op *opline, *end;
802 	int *tmp = NULL;
803 	ALLOCA_FLAG(use_heap = 0);
804 
805 	// FIXME: Can we optimize this copying out in some cases?
806 	if (blocks[n].next_child >= 0) {
807 		tmp = do_alloca(sizeof(int) * (op_array->last_var + op_array->T), use_heap);
808 		memcpy(tmp, var, sizeof(int) * (op_array->last_var + op_array->T));
809 		var = tmp;
810 	}
811 
812 	if (ssa_blocks[n].phis) {
813 		zend_ssa_phi *phi = ssa_blocks[n].phis;
814 		do {
815 			if (phi->ssa_var < 0) {
816 				phi->ssa_var = ssa_vars_count;
817 				var[phi->var] = ssa_vars_count;
818 				ssa_vars_count++;
819 			} else {
820 				var[phi->var] = phi->ssa_var;
821 			}
822 			phi = phi->next;
823 		} while (phi);
824 	}
825 
826 	opline = op_array->opcodes + blocks[n].start;
827 	end = opline + blocks[n].len;
828 	for (; opline < end; opline++) {
829 		uint32_t k = opline - op_array->opcodes;
830 		if (opline->opcode != ZEND_OP_DATA) {
831 			ssa_vars_count = _zend_ssa_rename_op(op_array, opline, k, build_flags, ssa_vars_count, ssa_ops, var);
832 		}
833 	}
834 
835 	zend_ssa_op *fe_fetch_ssa_op = blocks[n].len != 0
836 			&& ((end-1)->opcode == ZEND_FE_FETCH_R || (end-1)->opcode == ZEND_FE_FETCH_RW)
837 			&& (end-1)->op2_type == IS_CV
838 		? &ssa_ops[blocks[n].start + blocks[n].len - 1] : NULL;
839 	for (i = 0; i < blocks[n].successors_count; i++) {
840 		int succ = blocks[n].successors[i];
841 		zend_ssa_phi *p;
842 		for (p = ssa_blocks[succ].phis; p; p = p->next) {
843 			if (p->pi == n) {
844 				/* e-SSA Pi */
845 				if (p->has_range_constraint) {
846 					if (p->constraint.range.min_var >= 0) {
847 						p->constraint.range.min_ssa_var = var[p->constraint.range.min_var];
848 					}
849 					if (p->constraint.range.max_var >= 0) {
850 						p->constraint.range.max_ssa_var = var[p->constraint.range.max_var];
851 					}
852 				}
853 				for (j = 0; j < blocks[succ].predecessors_count; j++) {
854 					p->sources[j] = var[p->var];
855 				}
856 				if (p->ssa_var < 0) {
857 					p->ssa_var = ssa_vars_count;
858 					ssa_vars_count++;
859 				}
860 			} else if (p->pi < 0) {
861 				/* Normal Phi */
862 				for (j = 0; j < blocks[succ].predecessors_count; j++)
863 					if (ssa->cfg.predecessors[blocks[succ].predecessor_offset + j] == n) {
864 						break;
865 					}
866 				ZEND_ASSERT(j < blocks[succ].predecessors_count);
867 				p->sources[j] = var[p->var];
868 				if (fe_fetch_ssa_op && i == 0 && p->sources[j] == fe_fetch_ssa_op->op2_def) {
869 					/* On the exit edge of an FE_FETCH, use the pre-modification value instead. */
870 					p->sources[j] = fe_fetch_ssa_op->op2_use;
871 				}
872 			}
873 		}
874 		for (p = ssa_blocks[succ].phis; p && (p->pi >= 0); p = p->next) {
875 			if (p->pi == n) {
876 				zend_ssa_phi *q = p->next;
877 				while (q) {
878 					if (q->pi < 0 && q->var == p->var) {
879 						for (j = 0; j < blocks[succ].predecessors_count; j++) {
880 							if (ssa->cfg.predecessors[blocks[succ].predecessor_offset + j] == n) {
881 								break;
882 							}
883 						}
884 						ZEND_ASSERT(j < blocks[succ].predecessors_count);
885 						q->sources[j] = p->ssa_var;
886 					}
887 					q = q->next;
888 				}
889 			}
890 		}
891 	}
892 
893 	ssa->vars_count = ssa_vars_count;
894 
895 	j = blocks[n].children;
896 	while (j >= 0) {
897 		// FIXME: Tail call optimization?
898 		if (zend_ssa_rename(op_array, build_flags, ssa, var, j) != SUCCESS)
899 			return FAILURE;
900 		j = blocks[j].next_child;
901 	}
902 
903 	if (tmp) {
904 		free_alloca(tmp, use_heap);
905 	}
906 
907 	return SUCCESS;
908 }
909 /* }}} */
910 
zend_build_ssa(zend_arena ** arena,const zend_script * script,const zend_op_array * op_array,uint32_t build_flags,zend_ssa * ssa)911 int zend_build_ssa(zend_arena **arena, const zend_script *script, const zend_op_array *op_array, uint32_t build_flags, zend_ssa *ssa) /* {{{ */
912 {
913 	zend_basic_block *blocks = ssa->cfg.blocks;
914 	zend_ssa_block *ssa_blocks;
915 	int blocks_count = ssa->cfg.blocks_count;
916 	uint32_t set_size;
917 	zend_bitset def, in, phi;
918 	int *var = NULL;
919 	int i, j, k, changed;
920 	zend_dfg dfg;
921 	ALLOCA_FLAG(dfg_use_heap)
922 	ALLOCA_FLAG(var_use_heap)
923 
924 	if ((blocks_count * (op_array->last_var + op_array->T)) > 4 * 1024 * 1024) {
925 	    /* Don't build SSA for very big functions */
926 		return FAILURE;
927 	}
928 
929 	ssa_blocks = zend_arena_calloc(arena, blocks_count, sizeof(zend_ssa_block));
930 	ssa->blocks = ssa_blocks;
931 
932 	/* Compute Variable Liveness */
933 	dfg.vars = op_array->last_var + op_array->T;
934 	dfg.size = set_size = zend_bitset_len(dfg.vars);
935 	dfg.tmp = do_alloca((set_size * sizeof(zend_ulong)) * (blocks_count * 4 + 1), dfg_use_heap);
936 	memset(dfg.tmp, 0, (set_size * sizeof(zend_ulong)) * (blocks_count * 4 + 1));
937 	dfg.def = dfg.tmp + set_size;
938 	dfg.use = dfg.def + set_size * blocks_count;
939 	dfg.in  = dfg.use + set_size * blocks_count;
940 	dfg.out = dfg.in  + set_size * blocks_count;
941 
942 	if (zend_build_dfg(op_array, &ssa->cfg, &dfg, build_flags) != SUCCESS) {
943 		free_alloca(dfg.tmp, dfg_use_heap);
944 		return FAILURE;
945 	}
946 
947 	if (build_flags & ZEND_SSA_DEBUG_LIVENESS) {
948 		zend_dump_dfg(op_array, &ssa->cfg, &dfg);
949 	}
950 
951 	def = dfg.def;
952 	in  = dfg.in;
953 
954 	/* Reuse the "use" set, as we no longer need it */
955 	phi = dfg.use;
956 	zend_bitset_clear(phi, set_size * blocks_count);
957 
958 	/* Place e-SSA pis. This will add additional "def" points, so it must
959 	 * happen before def propagation. */
960 	place_essa_pis(arena, script, op_array, build_flags, ssa, &dfg);
961 
962 	/* SSA construction, Step 1: Propagate "def" sets in merge points */
963 	do {
964 		changed = 0;
965 		for (j = 0; j < blocks_count; j++) {
966 			zend_bitset def_j = def + j * set_size, phi_j = phi + j * set_size;
967 			if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
968 				continue;
969 			}
970 			if (blocks[j].predecessors_count > 1) {
971 				if (blocks[j].flags & ZEND_BB_IRREDUCIBLE_LOOP) {
972 					/* Prevent any values from flowing into irreducible loops by
973 					   replacing all incoming values with explicit phis.  The
974 					   register allocator depends on this property.  */
975 					zend_bitset_union(phi_j, in + (j * set_size), set_size);
976 				} else {
977 					for (k = 0; k < blocks[j].predecessors_count; k++) {
978 						i = ssa->cfg.predecessors[blocks[j].predecessor_offset + k];
979 						while (i != -1 && i != blocks[j].idom) {
980 							zend_bitset_union_with_intersection(
981 								phi_j, phi_j, def + (i * set_size), in + (j * set_size), set_size);
982 							i = blocks[i].idom;
983 						}
984 					}
985 				}
986 				if (!zend_bitset_subset(phi_j, def_j, set_size)) {
987 					zend_bitset_union(def_j, phi_j, set_size);
988 					changed = 1;
989 				}
990 			}
991 		}
992 	} while (changed);
993 
994 	/* SSA construction, Step 2: Phi placement based on Dominance Frontiers */
995 	var = do_alloca(sizeof(int) * (op_array->last_var + op_array->T), var_use_heap);
996 	if (!var) {
997 		free_alloca(dfg.tmp, dfg_use_heap);
998 		return FAILURE;
999 	}
1000 
1001 	for (j = 0; j < blocks_count; j++) {
1002 		if ((blocks[j].flags & ZEND_BB_REACHABLE) == 0) {
1003 			continue;
1004 		}
1005 		if (!zend_bitset_empty(phi + j * set_size, set_size)) {
1006 			ZEND_BITSET_REVERSE_FOREACH(phi + j * set_size, set_size, i) {
1007 				zend_ssa_phi *phi = zend_arena_calloc(arena, 1,
1008 					ZEND_MM_ALIGNED_SIZE(sizeof(zend_ssa_phi)) +
1009 					ZEND_MM_ALIGNED_SIZE(sizeof(int) * blocks[j].predecessors_count) +
1010 					sizeof(void*) * blocks[j].predecessors_count);
1011 
1012 				phi->sources = (int*)(((char*)phi) + ZEND_MM_ALIGNED_SIZE(sizeof(zend_ssa_phi)));
1013 				memset(phi->sources, 0xff, sizeof(int) * blocks[j].predecessors_count);
1014 				phi->use_chains = (zend_ssa_phi**)(((char*)phi->sources) + ZEND_MM_ALIGNED_SIZE(sizeof(int) * ssa->cfg.blocks[j].predecessors_count));
1015 
1016 				phi->pi = -1;
1017 				phi->var = i;
1018 				phi->ssa_var = -1;
1019 
1020 				/* Place phis after pis */
1021 				{
1022 					zend_ssa_phi **pp = &ssa_blocks[j].phis;
1023 					while (*pp) {
1024 						if ((*pp)->pi < 0) {
1025 							break;
1026 						}
1027 						pp = &(*pp)->next;
1028 					}
1029 					phi->next = *pp;
1030 					*pp = phi;
1031 				}
1032 			} ZEND_BITSET_FOREACH_END();
1033 		}
1034 	}
1035 
1036 	if (build_flags & ZEND_SSA_DEBUG_PHI_PLACEMENT) {
1037 		zend_dump_phi_placement(op_array, ssa);
1038 	}
1039 
1040 	/* SSA construction, Step 3: Renaming */
1041 	ssa->ops = zend_arena_calloc(arena, op_array->last, sizeof(zend_ssa_op));
1042 	memset(ssa->ops, 0xff, op_array->last * sizeof(zend_ssa_op));
1043 	memset(var + op_array->last_var, 0xff, op_array->T * sizeof(int));
1044 	/* Create uninitialized SSA variables for each CV */
1045 	for (j = 0; j < op_array->last_var; j++) {
1046 		var[j] = j;
1047 	}
1048 	ssa->vars_count = op_array->last_var;
1049 	if (zend_ssa_rename(op_array, build_flags, ssa, var, 0) != SUCCESS) {
1050 		free_alloca(var, var_use_heap);
1051 		free_alloca(dfg.tmp, dfg_use_heap);
1052 		return FAILURE;
1053 	}
1054 
1055 	free_alloca(var, var_use_heap);
1056 	free_alloca(dfg.tmp, dfg_use_heap);
1057 
1058 	return SUCCESS;
1059 }
1060 /* }}} */
1061 
zend_ssa_compute_use_def_chains(zend_arena ** arena,const zend_op_array * op_array,zend_ssa * ssa)1062 int zend_ssa_compute_use_def_chains(zend_arena **arena, const zend_op_array *op_array, zend_ssa *ssa) /* {{{ */
1063 {
1064 	zend_ssa_var *ssa_vars;
1065 	int i;
1066 
1067 	if (!ssa->vars) {
1068 		ssa->vars = zend_arena_calloc(arena, ssa->vars_count, sizeof(zend_ssa_var));
1069 	}
1070 	ssa_vars = ssa->vars;
1071 
1072 	for (i = 0; i < op_array->last_var; i++) {
1073 		ssa_vars[i].var = i;
1074 		ssa_vars[i].scc = -1;
1075 		ssa_vars[i].definition = -1;
1076 		ssa_vars[i].use_chain = -1;
1077 	}
1078 	for (i = op_array->last_var; i < ssa->vars_count; i++) {
1079 		ssa_vars[i].var = -1;
1080 		ssa_vars[i].scc = -1;
1081 		ssa_vars[i].definition = -1;
1082 		ssa_vars[i].use_chain = -1;
1083 	}
1084 
1085 	for (i = op_array->last - 1; i >= 0; i--) {
1086 		zend_ssa_op *op = ssa->ops + i;
1087 
1088 		if (op->op1_use >= 0) {
1089 			op->op1_use_chain = ssa_vars[op->op1_use].use_chain;
1090 			ssa_vars[op->op1_use].use_chain = i;
1091 		}
1092 		if (op->op2_use >= 0 && op->op2_use != op->op1_use) {
1093 			op->op2_use_chain = ssa_vars[op->op2_use].use_chain;
1094 			ssa_vars[op->op2_use].use_chain = i;
1095 		}
1096 		if (op->result_use >= 0 && op->result_use != op->op1_use && op->result_use != op->op2_use) {
1097 			op->res_use_chain = ssa_vars[op->result_use].use_chain;
1098 			ssa_vars[op->result_use].use_chain = i;
1099 		}
1100 		if (op->op1_def >= 0) {
1101 			ssa_vars[op->op1_def].var = EX_VAR_TO_NUM(op_array->opcodes[i].op1.var);
1102 			ssa_vars[op->op1_def].definition = i;
1103 		}
1104 		if (op->op2_def >= 0) {
1105 			ssa_vars[op->op2_def].var = EX_VAR_TO_NUM(op_array->opcodes[i].op2.var);
1106 			ssa_vars[op->op2_def].definition = i;
1107 		}
1108 		if (op->result_def >= 0) {
1109 			ssa_vars[op->result_def].var = EX_VAR_TO_NUM(op_array->opcodes[i].result.var);
1110 			ssa_vars[op->result_def].definition = i;
1111 		}
1112 	}
1113 
1114 	for (i = 0; i < ssa->cfg.blocks_count; i++) {
1115 		zend_ssa_phi *phi = ssa->blocks[i].phis;
1116 		while (phi) {
1117 			phi->block = i;
1118 			ssa_vars[phi->ssa_var].var = phi->var;
1119 			ssa_vars[phi->ssa_var].definition_phi = phi;
1120 			if (phi->pi >= 0) {
1121 				zend_ssa_phi *p;
1122 
1123 				ZEND_ASSERT(phi->sources[0] >= 0);
1124 				p = ssa_vars[phi->sources[0]].phi_use_chain;
1125 				while (p && p != phi) {
1126 					p = zend_ssa_next_use_phi(ssa, phi->sources[0], p);
1127 				}
1128 				if (!p) {
1129 					phi->use_chains[0] = ssa_vars[phi->sources[0]].phi_use_chain;
1130 					ssa_vars[phi->sources[0]].phi_use_chain = phi;
1131 				}
1132 				if (phi->has_range_constraint) {
1133 					/* min and max variables can't be used together */
1134 					zend_ssa_range_constraint *constraint = &phi->constraint.range;
1135 					if (constraint->min_ssa_var >= 0) {
1136 						phi->sym_use_chain = ssa_vars[constraint->min_ssa_var].sym_use_chain;
1137 						ssa_vars[constraint->min_ssa_var].sym_use_chain = phi;
1138 					} else if (constraint->max_ssa_var >= 0) {
1139 						phi->sym_use_chain = ssa_vars[constraint->max_ssa_var].sym_use_chain;
1140 						ssa_vars[constraint->max_ssa_var].sym_use_chain = phi;
1141 					}
1142 				}
1143 			} else {
1144 				int j;
1145 
1146 				for (j = 0; j < ssa->cfg.blocks[i].predecessors_count; j++) {
1147 					zend_ssa_phi *p;
1148 
1149 					ZEND_ASSERT(phi->sources[j] >= 0);
1150 					p = ssa_vars[phi->sources[j]].phi_use_chain;
1151 					while (p && p != phi) {
1152 						p = zend_ssa_next_use_phi(ssa, phi->sources[j], p);
1153 					}
1154 					if (!p) {
1155 						phi->use_chains[j] = ssa_vars[phi->sources[j]].phi_use_chain;
1156 						ssa_vars[phi->sources[j]].phi_use_chain = phi;
1157 					}
1158 				}
1159 			}
1160 			phi = phi->next;
1161 		}
1162 	}
1163 
1164 	/* Mark indirectly accessed variables */
1165 	for (i = 0; i < op_array->last_var; i++) {
1166 		if ((ssa->cfg.flags & ZEND_FUNC_INDIRECT_VAR_ACCESS)) {
1167 			ssa_vars[i].alias = SYMTABLE_ALIAS;
1168 		} else if (zend_string_equals_literal(op_array->vars[i], "http_response_header")) {
1169 			ssa_vars[i].alias = HTTP_RESPONSE_HEADER_ALIAS;
1170 		}
1171 	}
1172 	for (i = op_array->last_var; i < ssa->vars_count; i++) {
1173 		if (ssa_vars[i].var < op_array->last_var) {
1174 			ssa_vars[i].alias = ssa_vars[ssa_vars[i].var].alias;
1175 		}
1176 	}
1177 
1178 	return SUCCESS;
1179 }
1180 /* }}} */
1181 
zend_ssa_unlink_use_chain(zend_ssa * ssa,int op,int var)1182 int zend_ssa_unlink_use_chain(zend_ssa *ssa, int op, int var) /* {{{ */
1183 {
1184 	if (ssa->vars[var].use_chain == op) {
1185 		ssa->vars[var].use_chain = zend_ssa_next_use(ssa->ops, var, op);
1186 		return 1;
1187 	} else {
1188 		int use = ssa->vars[var].use_chain;
1189 
1190 		while (use >= 0) {
1191 			if (ssa->ops[use].result_use == var) {
1192 				if (ssa->ops[use].res_use_chain == op) {
1193 					ssa->ops[use].res_use_chain = zend_ssa_next_use(ssa->ops, var, op);
1194 					return 1;
1195 				} else {
1196 					use = ssa->ops[use].res_use_chain;
1197 				}
1198 			} else if (ssa->ops[use].op1_use == var) {
1199 				if (ssa->ops[use].op1_use_chain == op) {
1200 					ssa->ops[use].op1_use_chain = zend_ssa_next_use(ssa->ops, var, op);
1201 					return 1;
1202 				} else {
1203 					use = ssa->ops[use].op1_use_chain;
1204 				}
1205 			} else if (ssa->ops[use].op2_use == var) {
1206 				if (ssa->ops[use].op2_use_chain == op) {
1207 					ssa->ops[use].op2_use_chain = zend_ssa_next_use(ssa->ops, var, op);
1208 					return 1;
1209 				} else {
1210 					use = ssa->ops[use].op2_use_chain;
1211 				}
1212 			} else {
1213 				break;
1214 			}
1215 		}
1216 		/* something wrong */
1217 		ZEND_UNREACHABLE();
1218 		return 0;
1219 	}
1220 }
1221 /* }}} */
1222 
zend_ssa_remove_instr(zend_ssa * ssa,zend_op * opline,zend_ssa_op * ssa_op)1223 void zend_ssa_remove_instr(zend_ssa *ssa, zend_op *opline, zend_ssa_op *ssa_op) /* {{{ */
1224 {
1225 	if (ssa_op->result_use >= 0) {
1226 		zend_ssa_unlink_use_chain(ssa, ssa_op - ssa->ops, ssa_op->result_use);
1227 		ssa_op->result_use = -1;
1228 		ssa_op->res_use_chain = -1;
1229 	}
1230 	if (ssa_op->op1_use >= 0) {
1231 		if (ssa_op->op1_use != ssa_op->op2_use) {
1232 			zend_ssa_unlink_use_chain(ssa, ssa_op - ssa->ops, ssa_op->op1_use);
1233 		} else {
1234 			ssa_op->op2_use_chain = ssa_op->op1_use_chain;
1235 		}
1236 		ssa_op->op1_use = -1;
1237 		ssa_op->op1_use_chain = -1;
1238 	}
1239 	if (ssa_op->op2_use >= 0) {
1240 		zend_ssa_unlink_use_chain(ssa, ssa_op - ssa->ops, ssa_op->op2_use);
1241 		ssa_op->op2_use = -1;
1242 		ssa_op->op2_use_chain = -1;
1243 	}
1244 
1245 	/* We let the caller make sure that all defs are gone */
1246 	ZEND_ASSERT(ssa_op->result_def == -1);
1247 	ZEND_ASSERT(ssa_op->op1_def == -1);
1248 	ZEND_ASSERT(ssa_op->op2_def == -1);
1249 
1250 	MAKE_NOP(opline);
1251 }
1252 /* }}} */
1253 
zend_ssa_next_use_phi_ptr(zend_ssa * ssa,int var,zend_ssa_phi * p)1254 static inline zend_ssa_phi **zend_ssa_next_use_phi_ptr(zend_ssa *ssa, int var, zend_ssa_phi *p) /* {{{ */
1255 {
1256 	if (p->pi >= 0) {
1257 		return &p->use_chains[0];
1258 	} else {
1259 		int j;
1260 		for (j = 0; j < ssa->cfg.blocks[p->block].predecessors_count; j++) {
1261 			if (p->sources[j] == var) {
1262 				return &p->use_chains[j];
1263 			}
1264 		}
1265 	}
1266 	ZEND_UNREACHABLE();
1267 	return NULL;
1268 }
1269 /* }}} */
1270 
1271 /* May be called even if source is not used in the phi (useful when removing uses in a phi
1272  * with multiple identical operands) */
zend_ssa_remove_use_of_phi_source(zend_ssa * ssa,zend_ssa_phi * phi,int source,zend_ssa_phi * next_use_phi)1273 static inline void zend_ssa_remove_use_of_phi_source(zend_ssa *ssa, zend_ssa_phi *phi, int source, zend_ssa_phi *next_use_phi) /* {{{ */
1274 {
1275 	zend_ssa_phi **cur = &ssa->vars[source].phi_use_chain;
1276 	while (*cur && *cur != phi) {
1277 		cur = zend_ssa_next_use_phi_ptr(ssa, source, *cur);
1278 	}
1279 	if (*cur) {
1280 		*cur = next_use_phi;
1281 	}
1282 }
1283 /* }}} */
1284 
zend_ssa_remove_uses_of_phi_sources(zend_ssa * ssa,zend_ssa_phi * phi)1285 static void zend_ssa_remove_uses_of_phi_sources(zend_ssa *ssa, zend_ssa_phi *phi) /* {{{ */
1286 {
1287 	int source;
1288 	FOREACH_PHI_SOURCE(phi, source) {
1289 		zend_ssa_remove_use_of_phi_source(ssa, phi, source, zend_ssa_next_use_phi(ssa, source, phi));
1290 	} FOREACH_PHI_SOURCE_END();
1291 }
1292 /* }}} */
1293 
zend_ssa_remove_phi_from_block(zend_ssa * ssa,zend_ssa_phi * phi)1294 static void zend_ssa_remove_phi_from_block(zend_ssa *ssa, zend_ssa_phi *phi) /* {{{ */
1295 {
1296 	zend_ssa_block *block = &ssa->blocks[phi->block];
1297 	zend_ssa_phi **cur = &block->phis;
1298 	while (*cur != phi) {
1299 		ZEND_ASSERT(*cur != NULL);
1300 		cur = &(*cur)->next;
1301 	}
1302 	*cur = (*cur)->next;
1303 }
1304 /* }}} */
1305 
zend_ssa_remove_defs_of_instr(zend_ssa * ssa,zend_ssa_op * ssa_op)1306 static inline void zend_ssa_remove_defs_of_instr(zend_ssa *ssa, zend_ssa_op *ssa_op) /* {{{ */
1307 {
1308 	if (ssa_op->op1_def >= 0) {
1309 		zend_ssa_remove_uses_of_var(ssa, ssa_op->op1_def);
1310 		zend_ssa_remove_op1_def(ssa, ssa_op);
1311 	}
1312 	if (ssa_op->op2_def >= 0) {
1313 		zend_ssa_remove_uses_of_var(ssa, ssa_op->op2_def);
1314 		zend_ssa_remove_op2_def(ssa, ssa_op);
1315 	}
1316 	if (ssa_op->result_def >= 0) {
1317 		zend_ssa_remove_uses_of_var(ssa, ssa_op->result_def);
1318 		zend_ssa_remove_result_def(ssa, ssa_op);
1319 	}
1320 }
1321 /* }}} */
1322 
zend_ssa_remove_phi_source(zend_ssa * ssa,zend_ssa_phi * phi,int pred_offset,int predecessors_count)1323 static inline void zend_ssa_remove_phi_source(zend_ssa *ssa, zend_ssa_phi *phi, int pred_offset, int predecessors_count) /* {{{ */
1324 {
1325 	int j, var_num = phi->sources[pred_offset];
1326 	zend_ssa_phi *next_phi = phi->use_chains[pred_offset];
1327 
1328 	predecessors_count--;
1329 	if (pred_offset < predecessors_count) {
1330 		memmove(phi->sources + pred_offset, phi->sources + pred_offset + 1, (predecessors_count - pred_offset) * sizeof(uint32_t));
1331 		memmove(phi->use_chains + pred_offset, phi->use_chains + pred_offset + 1, (predecessors_count - pred_offset) * sizeof(zend_ssa_phi*));
1332 	}
1333 
1334 	/* Check if they same var is used in a different phi operand as well, in this case we don't
1335 	 * need to adjust the use chain (but may have to move the next pointer). */
1336 	for (j = 0; j < predecessors_count; j++) {
1337 		if (phi->sources[j] == var_num) {
1338 			if (j < pred_offset) {
1339 				ZEND_ASSERT(next_phi == NULL);
1340 			} else if (j >= pred_offset) {
1341 				phi->use_chains[j] = next_phi;
1342 			}
1343 			return;
1344 		}
1345 	}
1346 
1347 	/* Variable only used in one operand, remove the phi from the use chain. */
1348 	zend_ssa_remove_use_of_phi_source(ssa, phi, var_num, next_phi);
1349 }
1350 /* }}} */
1351 
zend_ssa_remove_phi(zend_ssa * ssa,zend_ssa_phi * phi)1352 void zend_ssa_remove_phi(zend_ssa *ssa, zend_ssa_phi *phi) /* {{{ */
1353 {
1354 	ZEND_ASSERT(phi->ssa_var >= 0);
1355 	ZEND_ASSERT(ssa->vars[phi->ssa_var].use_chain < 0
1356 		&& ssa->vars[phi->ssa_var].phi_use_chain == NULL);
1357 	zend_ssa_remove_uses_of_phi_sources(ssa, phi);
1358 	zend_ssa_remove_phi_from_block(ssa, phi);
1359 	ssa->vars[phi->ssa_var].definition_phi = NULL;
1360 	phi->ssa_var = -1;
1361 }
1362 /* }}} */
1363 
zend_ssa_remove_uses_of_var(zend_ssa * ssa,int var_num)1364 void zend_ssa_remove_uses_of_var(zend_ssa *ssa, int var_num) /* {{{ */
1365 {
1366 	zend_ssa_var *var = &ssa->vars[var_num];
1367 	zend_ssa_phi *phi;
1368 	int use;
1369 	FOREACH_PHI_USE(var, phi) {
1370 		int i, end = NUM_PHI_SOURCES(phi);
1371 		for (i = 0; i < end; i++) {
1372 			if (phi->sources[i] == var_num) {
1373 				phi->use_chains[i] = NULL;
1374 			}
1375 		}
1376 	} FOREACH_PHI_USE_END();
1377 	var->phi_use_chain = NULL;
1378 	FOREACH_USE(var, use) {
1379 		zend_ssa_op *ssa_op = &ssa->ops[use];
1380 		if (ssa_op->op1_use == var_num) {
1381 			ssa_op->op1_use = -1;
1382 			ssa_op->op1_use_chain = -1;
1383 		}
1384 		if (ssa_op->op2_use == var_num) {
1385 			ssa_op->op2_use = -1;
1386 			ssa_op->op2_use_chain = -1;
1387 		}
1388 		if (ssa_op->result_use == var_num) {
1389 			ssa_op->result_use = -1;
1390 			ssa_op->res_use_chain = -1;
1391 		}
1392 	} FOREACH_USE_END();
1393 	var->use_chain = -1;
1394 }
1395 /* }}} */
1396 
zend_ssa_remove_predecessor(zend_ssa * ssa,int from,int to)1397 void zend_ssa_remove_predecessor(zend_ssa *ssa, int from, int to) /* {{{ */
1398 {
1399 	zend_basic_block *next_block = &ssa->cfg.blocks[to];
1400 	zend_ssa_block *next_ssa_block = &ssa->blocks[to];
1401 	zend_ssa_phi *phi;
1402 	int j;
1403 
1404 	/* Find at which predecessor offset this block is referenced */
1405 	int pred_offset = -1;
1406 	int *predecessors = &ssa->cfg.predecessors[next_block->predecessor_offset];
1407 
1408 	for (j = 0; j < next_block->predecessors_count; j++) {
1409 		if (predecessors[j] == from) {
1410 			pred_offset = j;
1411 			break;
1412 		}
1413 	}
1414 
1415 	/* If there are duplicate successors, the predecessors may have been removed in
1416 	 * a previous iteration already. */
1417 	if (pred_offset == -1) {
1418 		return;
1419 	}
1420 
1421 	/* For phis in successor blocks, remove the operands associated with this block */
1422 	for (phi = next_ssa_block->phis; phi; phi = phi->next) {
1423 		if (phi->pi >= 0) {
1424 			if (phi->pi == from) {
1425 				zend_ssa_rename_var_uses(ssa, phi->ssa_var, phi->sources[0], /* update_types */ 0);
1426 				zend_ssa_remove_phi(ssa, phi);
1427 			}
1428 		} else {
1429 			ZEND_ASSERT(phi->sources[pred_offset] >= 0);
1430 			zend_ssa_remove_phi_source(ssa, phi, pred_offset, next_block->predecessors_count);
1431 		}
1432 	}
1433 
1434 	/* Remove this predecessor */
1435 	next_block->predecessors_count--;
1436 	if (pred_offset < next_block->predecessors_count) {
1437 		predecessors = &ssa->cfg.predecessors[next_block->predecessor_offset + pred_offset];
1438 		memmove(predecessors, predecessors + 1, (next_block->predecessors_count - pred_offset) * sizeof(uint32_t));
1439 	}
1440 }
1441 /* }}} */
1442 
zend_ssa_remove_block(zend_op_array * op_array,zend_ssa * ssa,int i)1443 void zend_ssa_remove_block(zend_op_array *op_array, zend_ssa *ssa, int i) /* {{{ */
1444 {
1445 	zend_basic_block *block = &ssa->cfg.blocks[i];
1446 	zend_ssa_block *ssa_block = &ssa->blocks[i];
1447 	int *predecessors;
1448 	zend_ssa_phi *phi;
1449 	int j, s;
1450 
1451 	block->flags &= ~ZEND_BB_REACHABLE;
1452 
1453 	/* Removes phis in this block */
1454 	for (phi = ssa_block->phis; phi; phi = phi->next) {
1455 		zend_ssa_remove_uses_of_var(ssa, phi->ssa_var);
1456 		zend_ssa_remove_phi(ssa, phi);
1457 	}
1458 
1459 	/* Remove instructions in this block */
1460 	for (j = block->start; j < block->start + block->len; j++) {
1461 		if (op_array->opcodes[j].opcode == ZEND_NOP) {
1462 			continue;
1463 		}
1464 
1465 		zend_ssa_remove_defs_of_instr(ssa, &ssa->ops[j]);
1466 		zend_ssa_remove_instr(ssa, &op_array->opcodes[j], &ssa->ops[j]);
1467 	}
1468 
1469 	for (s = 0; s < block->successors_count; s++) {
1470 		zend_ssa_remove_predecessor(ssa, i, block->successors[s]);
1471 	}
1472 
1473 	/* Remove successors of predecessors */
1474 	predecessors = &ssa->cfg.predecessors[block->predecessor_offset];
1475 	for (j = 0; j < block->predecessors_count; j++) {
1476 		if (predecessors[j] >= 0) {
1477 			zend_basic_block *prev_block = &ssa->cfg.blocks[predecessors[j]];
1478 
1479 			for (s = 0; s < prev_block->successors_count; s++) {
1480 				if (prev_block->successors[s] == i) {
1481 					memmove(prev_block->successors + s,
1482 							prev_block->successors + s + 1,
1483 							sizeof(int) * (prev_block->successors_count - s - 1));
1484 					prev_block->successors_count--;
1485 					s--;
1486 				}
1487 			}
1488 		}
1489 	}
1490 
1491 	block->successors_count = 0;
1492 	block->predecessors_count = 0;
1493 
1494 	/* Remove from dominators tree */
1495 	if (block->idom >= 0) {
1496 		j = ssa->cfg.blocks[block->idom].children;
1497 		if (j == i) {
1498 			ssa->cfg.blocks[block->idom].children = block->next_child;
1499 		} else if (j >= 0) {
1500 			while (ssa->cfg.blocks[j].next_child >= 0) {
1501 				if (ssa->cfg.blocks[j].next_child == i) {
1502 					ssa->cfg.blocks[j].next_child = block->next_child;
1503 					break;
1504 				}
1505 				j = ssa->cfg.blocks[j].next_child;
1506 			}
1507 		}
1508 	}
1509 	block->idom = -1;
1510 	block->level = -1;
1511 	block->children = -1;
1512 	block->next_child = -1;
1513 }
1514 /* }}} */
1515 
propagate_phi_type_widening(zend_ssa * ssa,int var)1516 static void propagate_phi_type_widening(zend_ssa *ssa, int var) /* {{{ */
1517 {
1518 	zend_ssa_phi *phi;
1519 	FOREACH_PHI_USE(&ssa->vars[var], phi) {
1520 		if (ssa->var_info[var].type & ~ssa->var_info[phi->ssa_var].type) {
1521 			ssa->var_info[phi->ssa_var].type |= ssa->var_info[var].type;
1522 			propagate_phi_type_widening(ssa, phi->ssa_var);
1523 		}
1524 	} FOREACH_PHI_USE_END();
1525 }
1526 /* }}} */
1527 
zend_ssa_rename_var_uses(zend_ssa * ssa,int old,int new,zend_bool update_types)1528 void zend_ssa_rename_var_uses(zend_ssa *ssa, int old, int new, zend_bool update_types) /* {{{ */
1529 {
1530 	zend_ssa_var *old_var = &ssa->vars[old];
1531 	zend_ssa_var *new_var = &ssa->vars[new];
1532 	int use;
1533 	zend_ssa_phi *phi;
1534 
1535 	ZEND_ASSERT(old >= 0 && new >= 0);
1536 	ZEND_ASSERT(old != new);
1537 
1538 	/* Only a no_val is both variables are */
1539 	new_var->no_val &= old_var->no_val;
1540 
1541 	/* Update ssa_op use chains */
1542 	FOREACH_USE(old_var, use) {
1543 		zend_ssa_op *ssa_op = &ssa->ops[use];
1544 
1545 		/* If the op already uses the new var, don't add the op to the use
1546 		 * list again. Instead move the use_chain to the correct operand. */
1547 		zend_bool add_to_use_chain = 1;
1548 		if (ssa_op->result_use == new) {
1549 			add_to_use_chain = 0;
1550 		} else if (ssa_op->op1_use == new) {
1551 			if (ssa_op->result_use == old) {
1552 				ssa_op->res_use_chain = ssa_op->op1_use_chain;
1553 				ssa_op->op1_use_chain = -1;
1554 			}
1555 			add_to_use_chain = 0;
1556 		} else if (ssa_op->op2_use == new) {
1557 			if (ssa_op->result_use == old) {
1558 				ssa_op->res_use_chain = ssa_op->op2_use_chain;
1559 				ssa_op->op2_use_chain = -1;
1560 			} else if (ssa_op->op1_use == old) {
1561 				ssa_op->op1_use_chain = ssa_op->op2_use_chain;
1562 				ssa_op->op2_use_chain = -1;
1563 			}
1564 			add_to_use_chain = 0;
1565 		}
1566 
1567 		/* Perform the actual renaming */
1568 		if (ssa_op->result_use == old) {
1569 			ssa_op->result_use = new;
1570 		}
1571 		if (ssa_op->op1_use == old) {
1572 			ssa_op->op1_use = new;
1573 		}
1574 		if (ssa_op->op2_use == old) {
1575 			ssa_op->op2_use = new;
1576 		}
1577 
1578 		/* Add op to use chain of new var (if it isn't already). We use the
1579 		 * first use chain of (result, op1, op2) that has the new variable. */
1580 		if (add_to_use_chain) {
1581 			if (ssa_op->result_use == new) {
1582 				ssa_op->res_use_chain = new_var->use_chain;
1583 				new_var->use_chain = use;
1584 			} else if (ssa_op->op1_use == new) {
1585 				ssa_op->op1_use_chain = new_var->use_chain;
1586 				new_var->use_chain = use;
1587 			} else {
1588 				ZEND_ASSERT(ssa_op->op2_use == new);
1589 				ssa_op->op2_use_chain = new_var->use_chain;
1590 				new_var->use_chain = use;
1591 			}
1592 		}
1593 	} FOREACH_USE_END();
1594 	old_var->use_chain = -1;
1595 
1596 	/* Update phi use chains */
1597 	FOREACH_PHI_USE(old_var, phi) {
1598 		int j;
1599 		zend_bool after_first_new_source = 0;
1600 
1601 		/* If the phi already uses the new var, find its use chain, as we may
1602 		 * need to move it to a different source operand. */
1603 		zend_ssa_phi **existing_use_chain_ptr = NULL;
1604 		for (j = 0; j < ssa->cfg.blocks[phi->block].predecessors_count; j++) {
1605 			if (phi->sources[j] == new) {
1606 				existing_use_chain_ptr = &phi->use_chains[j];
1607 				break;
1608 			}
1609 		}
1610 
1611 		for (j = 0; j < ssa->cfg.blocks[phi->block].predecessors_count; j++) {
1612 			if (phi->sources[j] == new) {
1613 				after_first_new_source = 1;
1614 			} else if (phi->sources[j] == old) {
1615 				phi->sources[j] = new;
1616 
1617 				/* Either move existing use chain to this source, or add the phi
1618 				 * to the phi use chain of the new variables. Do this only once. */
1619 				if (!after_first_new_source) {
1620 					if (existing_use_chain_ptr) {
1621 						phi->use_chains[j] = *existing_use_chain_ptr;
1622 						*existing_use_chain_ptr = NULL;
1623 					} else {
1624 						phi->use_chains[j] = new_var->phi_use_chain;
1625 						new_var->phi_use_chain = phi;
1626 					}
1627 					after_first_new_source = 1;
1628 				} else {
1629 					phi->use_chains[j] = NULL;
1630 				}
1631 			}
1632 		}
1633 
1634 		/* Make sure phi result types are not incorrectly narrow after renaming.
1635 		 * This should not normally happen, but can occur if we DCE an assignment
1636 		 * or unset and there is an improper phi-indirected use lateron. */
1637 		// TODO Alternatively we could rerun type-inference after DCE
1638 		if (update_types && (ssa->var_info[new].type & ~ssa->var_info[phi->ssa_var].type)) {
1639 			ssa->var_info[phi->ssa_var].type |= ssa->var_info[new].type;
1640 			propagate_phi_type_widening(ssa, phi->ssa_var);
1641 		}
1642 	} FOREACH_PHI_USE_END();
1643 	old_var->phi_use_chain = NULL;
1644 }
1645 /* }}} */
1646