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