xref: /PHP-8.1/Zend/Optimizer/dce.c (revision 56d7672d)
1 /*
2    +----------------------------------------------------------------------+
3    | Zend Engine, DCE - Dead Code Elimination                             |
4    +----------------------------------------------------------------------+
5    | Copyright (c) The PHP Group                                          |
6    +----------------------------------------------------------------------+
7    | This source file is subject to version 3.01 of the PHP license,      |
8    | that is bundled with this package in the file LICENSE, and is        |
9    | available through the world-wide-web at the following url:           |
10    | https://www.php.net/license/3_01.txt                                 |
11    | If you did not receive a copy of the PHP license and are unable to   |
12    | obtain it through the world-wide-web, please send a note to          |
13    | license@php.net so we can mail you a copy immediately.               |
14    +----------------------------------------------------------------------+
15    | Authors: Nikita Popov <nikic@php.net>                                |
16    |          Dmitry Stogov <dmitry@php.net>                              |
17    +----------------------------------------------------------------------+
18 */
19 
20 #include "Optimizer/zend_optimizer_internal.h"
21 #include "Optimizer/zend_inference.h"
22 #include "Optimizer/zend_ssa.h"
23 #include "Optimizer/zend_func_info.h"
24 #include "Optimizer/zend_call_graph.h"
25 #include "zend_bitset.h"
26 
27 /* This pass implements a form of dead code elimination (DCE). The algorithm optimistically assumes
28  * that all instructions and phis are dead. Instructions with immediate side-effects are then marked
29  * as live. We then recursively (using a worklist) propagate liveness to the instructions that def
30  * the used operands.
31  *
32  * Notes:
33  *  * This pass does not perform unreachable code elimination. This happens as part of the SCCP
34  *    pass.
35  *  * The DCE is performed without taking control-dependence into account, i.e. all conditional
36  *    branches are assumed to be live. It's possible to take control-dependence into account using
37  *    the DCE algorithm described by Cytron et al., however it requires the construction of a
38  *    postdominator tree and of postdominance frontiers, which does not seem worthwhile at this
39  *    point.
40  *  * We separate intrinsic side-effects from potential side-effects in the form of notices thrown
41  *    by the instruction (in case we want to make this configurable). See may_have_side_effects() and
42  *    zend_may_throw().
43  *  * We often cannot DCE assignments and unsets while guaranteeing that dtors run in the same
44  *    order. There is an optimization option to allow reordering of dtor effects.
45  *  * The algorithm is able to eliminate dead modifications of non-escaping arrays
46  *    and objects as well as dead arrays and objects allocations.
47  */
48 
49 typedef struct {
50 	zend_ssa *ssa;
51 	zend_op_array *op_array;
52 	zend_bitset instr_dead;
53 	zend_bitset phi_dead;
54 	zend_bitset instr_worklist;
55 	zend_bitset phi_worklist;
56 	zend_bitset phi_worklist_no_val;
57 	uint32_t instr_worklist_len;
58 	uint32_t phi_worklist_len;
59 	unsigned reorder_dtor_effects : 1;
60 } context;
61 
is_bad_mod(const zend_ssa * ssa,int use,int def)62 static inline bool is_bad_mod(const zend_ssa *ssa, int use, int def) {
63 	if (def < 0) {
64 		/* This modification is not tracked by SSA, assume the worst */
65 		return 1;
66 	}
67 	if (ssa->var_info[use].type & MAY_BE_REF) {
68 		/* Modification of reference may have side-effect */
69 		return 1;
70 	}
71 	return 0;
72 }
73 
may_have_side_effects(zend_op_array * op_array,zend_ssa * ssa,const zend_op * opline,const zend_ssa_op * ssa_op,bool reorder_dtor_effects)74 static inline bool may_have_side_effects(
75 		zend_op_array *op_array, zend_ssa *ssa,
76 		const zend_op *opline, const zend_ssa_op *ssa_op,
77 		bool reorder_dtor_effects) {
78 	switch (opline->opcode) {
79 		case ZEND_NOP:
80 		case ZEND_IS_IDENTICAL:
81 		case ZEND_IS_NOT_IDENTICAL:
82 		case ZEND_QM_ASSIGN:
83 		case ZEND_FREE:
84 		case ZEND_FE_FREE:
85 		case ZEND_TYPE_CHECK:
86 		case ZEND_DEFINED:
87 		case ZEND_ADD:
88 		case ZEND_SUB:
89 		case ZEND_MUL:
90 		case ZEND_POW:
91 		case ZEND_BW_OR:
92 		case ZEND_BW_AND:
93 		case ZEND_BW_XOR:
94 		case ZEND_CONCAT:
95 		case ZEND_FAST_CONCAT:
96 		case ZEND_DIV:
97 		case ZEND_MOD:
98 		case ZEND_BOOL_XOR:
99 		case ZEND_BOOL:
100 		case ZEND_BOOL_NOT:
101 		case ZEND_BW_NOT:
102 		case ZEND_SL:
103 		case ZEND_SR:
104 		case ZEND_IS_EQUAL:
105 		case ZEND_IS_NOT_EQUAL:
106 		case ZEND_IS_SMALLER:
107 		case ZEND_IS_SMALLER_OR_EQUAL:
108 		case ZEND_CASE:
109 		case ZEND_CASE_STRICT:
110 		case ZEND_CAST:
111 		case ZEND_ROPE_INIT:
112 		case ZEND_ROPE_ADD:
113 		case ZEND_INIT_ARRAY:
114 		case ZEND_SPACESHIP:
115 		case ZEND_STRLEN:
116 		case ZEND_COUNT:
117 		case ZEND_GET_TYPE:
118 		case ZEND_ISSET_ISEMPTY_THIS:
119 		case ZEND_ISSET_ISEMPTY_DIM_OBJ:
120 		case ZEND_FETCH_DIM_IS:
121 		case ZEND_ISSET_ISEMPTY_CV:
122 		case ZEND_ISSET_ISEMPTY_VAR:
123 		case ZEND_FETCH_IS:
124 		case ZEND_IN_ARRAY:
125 		case ZEND_FUNC_NUM_ARGS:
126 		case ZEND_FUNC_GET_ARGS:
127 		case ZEND_ARRAY_KEY_EXISTS:
128 			/* No side effects */
129 			return 0;
130 		case ZEND_ADD_ARRAY_ELEMENT:
131 			/* TODO: We can't free two vars. Keep instruction alive. <?php [0, "$a" => "$b"]; */
132 			if ((opline->op1_type & (IS_VAR|IS_TMP_VAR)) && (opline->op2_type & (IS_VAR|IS_TMP_VAR))) {
133 				return 1;
134 			}
135 			return 0;
136 		case ZEND_ROPE_END:
137 			/* TODO: Rope dce optimization, see #76446 */
138 			return 1;
139 		case ZEND_JMP:
140 		case ZEND_JMPZ:
141 		case ZEND_JMPNZ:
142 		case ZEND_JMPZNZ:
143 		case ZEND_JMPZ_EX:
144 		case ZEND_JMPNZ_EX:
145 		case ZEND_JMP_SET:
146 		case ZEND_COALESCE:
147 		case ZEND_ASSERT_CHECK:
148 		case ZEND_JMP_NULL:
149 			/* For our purposes a jumps and branches are side effects. */
150 			return 1;
151 		case ZEND_BEGIN_SILENCE:
152 		case ZEND_END_SILENCE:
153 		case ZEND_ECHO:
154 		case ZEND_INCLUDE_OR_EVAL:
155 		case ZEND_THROW:
156 		case ZEND_MATCH_ERROR:
157 		case ZEND_EXT_STMT:
158 		case ZEND_EXT_FCALL_BEGIN:
159 		case ZEND_EXT_FCALL_END:
160 		case ZEND_TICKS:
161 		case ZEND_YIELD:
162 		case ZEND_YIELD_FROM:
163 		case ZEND_VERIFY_NEVER_TYPE:
164 			/* Intrinsic side effects */
165 			return 1;
166 		case ZEND_DO_FCALL:
167 		case ZEND_DO_FCALL_BY_NAME:
168 		case ZEND_DO_ICALL:
169 		case ZEND_DO_UCALL:
170 			/* For now assume all calls have side effects */
171 			return 1;
172 		case ZEND_RECV:
173 		case ZEND_RECV_INIT:
174 			/* Even though RECV_INIT can be side-effect free, these cannot be simply dropped
175 			 * due to the prologue skipping code. */
176 			return 1;
177 		case ZEND_ASSIGN_REF:
178 			return 1;
179 		case ZEND_ASSIGN:
180 		{
181 			if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)) {
182 				return 1;
183 			}
184 			if (!reorder_dtor_effects) {
185 				if (opline->op2_type != IS_CONST
186 					&& (OP2_INFO() & MAY_HAVE_DTOR)
187 					&& ssa->vars[ssa_op->op2_use].escape_state != ESCAPE_STATE_NO_ESCAPE) {
188 					/* DCE might shorten lifetime */
189 					return 1;
190 				}
191 			}
192 			return 0;
193 		}
194 		case ZEND_UNSET_VAR:
195 			return 1;
196 		case ZEND_UNSET_CV:
197 		{
198 			uint32_t t1 = OP1_INFO();
199 			if (t1 & MAY_BE_REF) {
200 				/* We don't consider uses as the LHS of an assignment as real uses during DCE, so
201 				 * an unset may be considered dead even if there is a later assignment to the
202 				 * variable. Removing the unset in this case would not be correct if the variable
203 				 * is a reference, because unset breaks references. */
204 				return 1;
205 			}
206 			return 0;
207 		}
208 		case ZEND_PRE_INC:
209 		case ZEND_POST_INC:
210 		case ZEND_PRE_DEC:
211 		case ZEND_POST_DEC:
212 			return is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def);
213 		case ZEND_ASSIGN_OP:
214 			return is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)
215 				|| ssa->vars[ssa_op->op1_def].escape_state != ESCAPE_STATE_NO_ESCAPE;
216 		case ZEND_ASSIGN_DIM:
217 		case ZEND_ASSIGN_OBJ:
218 			if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)
219 				|| ssa->vars[ssa_op->op1_def].escape_state != ESCAPE_STATE_NO_ESCAPE) {
220 				return 1;
221 			}
222 			if (!reorder_dtor_effects) {
223 				opline++;
224 				ssa_op++;
225 				if (opline->op1_type != IS_CONST
226 					&& (OP1_INFO() & MAY_HAVE_DTOR)) {
227 					/* DCE might shorten lifetime */
228 					return 1;
229 				}
230 			}
231 			return 0;
232 		case ZEND_PRE_INC_OBJ:
233 		case ZEND_PRE_DEC_OBJ:
234 		case ZEND_POST_INC_OBJ:
235 		case ZEND_POST_DEC_OBJ:
236 			if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)
237 				|| ssa->vars[ssa_op->op1_def].escape_state != ESCAPE_STATE_NO_ESCAPE) {
238 				return 1;
239 			}
240 			return 0;
241 		case ZEND_BIND_STATIC:
242 			if (op_array->static_variables) {
243 				/* Implicit and Explicit bind static is effectively prologue of closure so
244 				   report it has side effects like RECV, RECV_INIT; This allows us to
245 				   reflect on the closure and discover used variable at runtime */
246 				if ((opline->extended_value & (ZEND_BIND_IMPLICIT|ZEND_BIND_EXPLICIT))) {
247 					return 1;
248 				}
249 
250 				if ((opline->extended_value & ZEND_BIND_REF) != 0) {
251 					zval *value =
252 						(zval*)((char*)op_array->static_variables->arData +
253 							(opline->extended_value & ~ZEND_BIND_REF));
254 					if (Z_TYPE_P(value) == IS_CONSTANT_AST) {
255 						/* AST may contain undefined constants */
256 						return 1;
257 					}
258 				}
259 			}
260 			return 0;
261 		case ZEND_CHECK_VAR:
262 			return (OP1_INFO() & MAY_BE_UNDEF) != 0;
263 		case ZEND_FE_RESET_R:
264 		case ZEND_FE_RESET_RW:
265 			/* Model as not having side-effects -- let the side-effect be introduced by
266 			 * FE_FETCH if the array is not known to be non-empty. */
267 			return (OP1_INFO() & MAY_BE_ANY) != MAY_BE_ARRAY;
268 		default:
269 			/* For everything we didn't handle, assume a side-effect */
270 			return 1;
271 	}
272 }
273 
add_to_worklists(context * ctx,int var_num,int check)274 static zend_always_inline void add_to_worklists(context *ctx, int var_num, int check) {
275 	zend_ssa_var *var = &ctx->ssa->vars[var_num];
276 	if (var->definition >= 0) {
277 		if (!check || zend_bitset_in(ctx->instr_dead, var->definition)) {
278 			zend_bitset_incl(ctx->instr_worklist, var->definition);
279 		}
280 	} else if (var->definition_phi) {
281 		if (!check || zend_bitset_in(ctx->phi_dead, var_num)) {
282 			zend_bitset_incl(ctx->phi_worklist, var_num);
283 		}
284 	}
285 }
286 
add_to_phi_worklist_no_val(context * ctx,int var_num)287 static inline void add_to_phi_worklist_no_val(context *ctx, int var_num) {
288 	zend_ssa_var *var = &ctx->ssa->vars[var_num];
289 	if (var->definition_phi && zend_bitset_in(ctx->phi_dead, var_num)) {
290 		zend_bitset_incl(ctx->phi_worklist_no_val, var_num);
291 	}
292 }
293 
add_operands_to_worklists(context * ctx,zend_op * opline,zend_ssa_op * ssa_op,zend_ssa * ssa,int check)294 static zend_always_inline void add_operands_to_worklists(context *ctx, zend_op *opline, zend_ssa_op *ssa_op, zend_ssa *ssa, int check) {
295 	if (ssa_op->result_use >= 0) {
296 		add_to_worklists(ctx, ssa_op->result_use, check);
297 	}
298 	if (ssa_op->op1_use >= 0) {
299 		if (!zend_ssa_is_no_val_use(opline, ssa_op, ssa_op->op1_use)
300 		 || (opline->opcode == ZEND_ASSIGN
301 		  && (ssa->var_info[ssa_op->op1_use].type & MAY_BE_REF) != 0)) {
302 			add_to_worklists(ctx, ssa_op->op1_use, check);
303 		} else {
304 			add_to_phi_worklist_no_val(ctx, ssa_op->op1_use);
305 		}
306 	}
307 	if (ssa_op->op2_use >= 0) {
308 		if (!zend_ssa_is_no_val_use(opline, ssa_op, ssa_op->op2_use)
309 		 || (opline->opcode == ZEND_FE_FETCH_R
310 		  && (ssa->var_info[ssa_op->op2_use].type & MAY_BE_REF) != 0)) {
311 			add_to_worklists(ctx, ssa_op->op2_use, check);
312 		} else {
313 			add_to_phi_worklist_no_val(ctx, ssa_op->op2_use);
314 		}
315 	}
316 }
317 
add_phi_sources_to_worklists(context * ctx,zend_ssa_phi * phi,int check)318 static zend_always_inline void add_phi_sources_to_worklists(context *ctx, zend_ssa_phi *phi, int check) {
319 	zend_ssa *ssa = ctx->ssa;
320 	int source;
321 	FOREACH_PHI_SOURCE(phi, source) {
322 		add_to_worklists(ctx, source, check);
323 	} FOREACH_PHI_SOURCE_END();
324 }
325 
is_var_dead(context * ctx,int var_num)326 static inline bool is_var_dead(context *ctx, int var_num) {
327 	zend_ssa_var *var = &ctx->ssa->vars[var_num];
328 	if (var->definition_phi) {
329 		return zend_bitset_in(ctx->phi_dead, var_num);
330 	} else if (var->definition >= 0) {
331 		return zend_bitset_in(ctx->instr_dead, var->definition);
332 	} else {
333 		/* Variable has no definition, so either the definition has already been removed (var is
334 		 * dead) or this is one of the implicit variables at the start of the function (for our
335 		 * purposes live) */
336 		return var_num >= ctx->op_array->last_var;
337 	}
338 }
339 
340 // Sometimes we can mark the var as EXT_UNUSED
try_remove_var_def(context * ctx,int free_var,int use_chain,zend_op * opline)341 static bool try_remove_var_def(context *ctx, int free_var, int use_chain, zend_op *opline) {
342 	if (use_chain >= 0) {
343 		return 0;
344 	}
345 	zend_ssa_var *var = &ctx->ssa->vars[free_var];
346 	int def = var->definition;
347 
348 	if (def >= 0) {
349 		zend_ssa_op *def_op = &ctx->ssa->ops[def];
350 
351 		if (def_op->result_def == free_var
352 				&& var->phi_use_chain == NULL
353 				&& var->use_chain == (opline - ctx->op_array->opcodes)) {
354 			zend_op *def_opline = &ctx->op_array->opcodes[def];
355 
356 			switch (def_opline->opcode) {
357 				case ZEND_ASSIGN:
358 				case ZEND_ASSIGN_REF:
359 				case ZEND_ASSIGN_DIM:
360 				case ZEND_ASSIGN_OBJ:
361 				case ZEND_ASSIGN_OBJ_REF:
362 				case ZEND_ASSIGN_STATIC_PROP:
363 				case ZEND_ASSIGN_STATIC_PROP_REF:
364 				case ZEND_ASSIGN_OP:
365 				case ZEND_ASSIGN_DIM_OP:
366 				case ZEND_ASSIGN_OBJ_OP:
367 				case ZEND_ASSIGN_STATIC_PROP_OP:
368 				case ZEND_PRE_INC:
369 				case ZEND_PRE_DEC:
370 				case ZEND_PRE_INC_OBJ:
371 				case ZEND_PRE_DEC_OBJ:
372 				case ZEND_DO_ICALL:
373 				case ZEND_DO_UCALL:
374 				case ZEND_DO_FCALL_BY_NAME:
375 				case ZEND_DO_FCALL:
376 				case ZEND_INCLUDE_OR_EVAL:
377 				case ZEND_YIELD:
378 				case ZEND_YIELD_FROM:
379 				case ZEND_ASSERT_CHECK:
380 					def_opline->result_type = IS_UNUSED;
381 					def_opline->result.var = 0;
382 					def_op->result_def = -1;
383 					var->definition = -1;
384 					return 1;
385 				default:
386 					break;
387 			}
388 		}
389 	}
390 	return 0;
391 }
392 
may_be_refcounted(uint32_t type)393 static zend_always_inline bool may_be_refcounted(uint32_t type) {
394 	return (type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF)) != 0;
395 }
396 
is_free_of_live_var(context * ctx,zend_op * opline,zend_ssa_op * ssa_op)397 static inline bool is_free_of_live_var(context *ctx, zend_op *opline, zend_ssa_op *ssa_op) {
398 	switch (opline->opcode) {
399 		case ZEND_FREE:
400 			/* It is always safe to remove FREEs of non-refcounted values, even if they are live. */
401 			if ((ctx->ssa->var_info[ssa_op->op1_use].type & (MAY_BE_REF|MAY_BE_ANY|MAY_BE_UNDEF)) != 0
402 			 && !may_be_refcounted(ctx->ssa->var_info[ssa_op->op1_use].type)) {
403 				return 0;
404 			}
405 			ZEND_FALLTHROUGH;
406 		case ZEND_FE_FREE:
407 			return !is_var_dead(ctx, ssa_op->op1_use);
408 		default:
409 			return 0;
410 	}
411 }
412 
413 /* Returns whether the instruction has been DCEd */
dce_instr(context * ctx,zend_op * opline,zend_ssa_op * ssa_op)414 static bool dce_instr(context *ctx, zend_op *opline, zend_ssa_op *ssa_op) {
415 	zend_ssa *ssa = ctx->ssa;
416 	int free_var = -1;
417 	zend_uchar free_var_type;
418 
419 	if (opline->opcode == ZEND_NOP) {
420 		return 0;
421 	}
422 
423 	/* We mark FREEs as dead, but they're only really dead if the destroyed var is dead */
424 	if (is_free_of_live_var(ctx, opline, ssa_op)) {
425 		return 0;
426 	}
427 
428 	if ((opline->op1_type & (IS_VAR|IS_TMP_VAR))&& !is_var_dead(ctx, ssa_op->op1_use)) {
429 		if (!try_remove_var_def(ctx, ssa_op->op1_use, ssa_op->op1_use_chain, opline)) {
430 			if (may_be_refcounted(ssa->var_info[ssa_op->op1_use].type)
431 					&& opline->opcode != ZEND_CASE && opline->opcode != ZEND_CASE_STRICT) {
432 				free_var = ssa_op->op1_use;
433 				free_var_type = opline->op1_type;
434 			}
435 		}
436 	}
437 	if ((opline->op2_type & (IS_VAR|IS_TMP_VAR)) && !is_var_dead(ctx, ssa_op->op2_use)) {
438 		if (!try_remove_var_def(ctx, ssa_op->op2_use, ssa_op->op2_use_chain, opline)) {
439 			if (may_be_refcounted(ssa->var_info[ssa_op->op2_use].type)) {
440 				if (free_var >= 0) {
441 					// TODO: We can't free two vars. Keep instruction alive.
442 					zend_bitset_excl(ctx->instr_dead, opline - ctx->op_array->opcodes);
443 					return 0;
444 				}
445 				free_var = ssa_op->op2_use;
446 				free_var_type = opline->op2_type;
447 			}
448 		}
449 	}
450 
451 	zend_ssa_rename_defs_of_instr(ctx->ssa, ssa_op);
452 	zend_ssa_remove_instr(ctx->ssa, opline, ssa_op);
453 
454 	if (free_var >= 0) {
455 		opline->opcode = ZEND_FREE;
456 		opline->op1.var = EX_NUM_TO_VAR(ssa->vars[free_var].var);
457 		opline->op1_type = free_var_type;
458 
459 		ssa_op->op1_use = free_var;
460 		ssa_op->op1_use_chain = ssa->vars[free_var].use_chain;
461 		ssa->vars[free_var].use_chain = ssa_op - ssa->ops;
462 		return 0;
463 	}
464 	return 1;
465 }
466 
get_common_phi_source(zend_ssa * ssa,zend_ssa_phi * phi)467 static inline int get_common_phi_source(zend_ssa *ssa, zend_ssa_phi *phi) {
468 	int common_source = -1;
469 	int source;
470 	FOREACH_PHI_SOURCE(phi, source) {
471 		if (source == phi->ssa_var) {
472 			continue;
473 		}
474 		if (common_source == -1) {
475 			common_source = source;
476 		} else if (common_source != source) {
477 			return -1;
478 		}
479 	} FOREACH_PHI_SOURCE_END();
480 
481 	/* If all sources are phi->ssa_var this phi must be in an unreachable cycle.
482 	 * We can't easily drop the phi in that case, as we don't have something to replace it with.
483 	 * Ideally SCCP would eliminate the whole cycle. */
484 	return common_source;
485 }
486 
try_remove_trivial_phi(context * ctx,zend_ssa_phi * phi)487 static void try_remove_trivial_phi(context *ctx, zend_ssa_phi *phi) {
488 	zend_ssa *ssa = ctx->ssa;
489 	if (phi->pi < 0) {
490 		/* Phi assignment with identical source operands */
491 		int common_source = get_common_phi_source(ssa, phi);
492 		if (common_source >= 0) {
493 			zend_ssa_rename_var_uses(ssa, phi->ssa_var, common_source, 1);
494 			zend_ssa_remove_phi(ssa, phi);
495 		}
496 	} else {
497 		/* Pi assignment that is only used in Phi/Pi assignments */
498 		// TODO What if we want to rerun type inference after DCE? Maybe separate this?
499 		/*ZEND_ASSERT(phi->sources[0] != -1);
500 		if (ssa->vars[phi->ssa_var].use_chain < 0) {
501 			zend_ssa_rename_var_uses_keep_types(ssa, phi->ssa_var, phi->sources[0], 1);
502 			zend_ssa_remove_phi(ssa, phi);
503 		}*/
504 	}
505 }
506 
may_break_varargs(const zend_op_array * op_array,const zend_ssa * ssa,const zend_ssa_op * ssa_op)507 static inline bool may_break_varargs(const zend_op_array *op_array, const zend_ssa *ssa, const zend_ssa_op *ssa_op) {
508 	if (ssa_op->op1_def >= 0
509 			&& ssa->vars[ssa_op->op1_def].var < op_array->num_args) {
510 		return 1;
511 	}
512 	if (ssa_op->op2_def >= 0
513 			&& ssa->vars[ssa_op->op2_def].var < op_array->num_args) {
514 		return 1;
515 	}
516 	if (ssa_op->result_def >= 0
517 			&& ssa->vars[ssa_op->result_def].var < op_array->num_args) {
518 		return 1;
519 	}
520 	return 0;
521 }
522 
may_throw_dce_exception(const zend_op * opline)523 static inline bool may_throw_dce_exception(const zend_op *opline) {
524 	return opline->opcode == ZEND_ADD_ARRAY_ELEMENT && opline->op2_type == IS_UNUSED;
525 }
526 
dce_optimize_op_array(zend_op_array * op_array,zend_ssa * ssa,bool reorder_dtor_effects)527 int dce_optimize_op_array(zend_op_array *op_array, zend_ssa *ssa, bool reorder_dtor_effects) {
528 	int i;
529 	zend_ssa_phi *phi;
530 	int removed_ops = 0;
531 
532 	/* DCE of CV operations that changes arguments may affect vararg functions. */
533 	bool has_varargs = (ssa->cfg.flags & ZEND_FUNC_VARARG) != 0;
534 
535 	context ctx;
536 	ctx.ssa = ssa;
537 	ctx.op_array = op_array;
538 	ctx.reorder_dtor_effects = reorder_dtor_effects;
539 
540 	/* We have no dedicated phi vector, so we use the whole ssa var vector instead */
541 	ctx.instr_worklist_len = zend_bitset_len(op_array->last);
542 	ctx.instr_worklist = alloca(sizeof(zend_ulong) * ctx.instr_worklist_len);
543 	memset(ctx.instr_worklist, 0, sizeof(zend_ulong) * ctx.instr_worklist_len);
544 	ctx.phi_worklist_len = zend_bitset_len(ssa->vars_count);
545 	ctx.phi_worklist = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len);
546 	memset(ctx.phi_worklist, 0, sizeof(zend_ulong) * ctx.phi_worklist_len);
547 	ctx.phi_worklist_no_val = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len);
548 	memset(ctx.phi_worklist_no_val, 0, sizeof(zend_ulong) * ctx.phi_worklist_len);
549 
550 	/* Optimistically assume all instructions and phis to be dead */
551 	ctx.instr_dead = alloca(sizeof(zend_ulong) * ctx.instr_worklist_len);
552 	memset(ctx.instr_dead, 0, sizeof(zend_ulong) * ctx.instr_worklist_len);
553 	ctx.phi_dead = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len);
554 	memset(ctx.phi_dead, 0xff, sizeof(zend_ulong) * ctx.phi_worklist_len);
555 
556 	/* Mark non-CV phis as live. Even if the result is unused, we generally cannot remove one
557 	 * of the producing instructions, as it combines producing the result with control flow.
558 	 * This can be made more precise if there are any cases where this is not the case. */
559 	FOREACH_PHI(phi) {
560 		if (phi->var >= op_array->last_var
561 				&& may_be_refcounted(ssa->var_info[phi->ssa_var].type)) {
562 			zend_bitset_excl(ctx.phi_dead, phi->ssa_var);
563 			add_phi_sources_to_worklists(&ctx, phi, 0);
564 		}
565 	} FOREACH_PHI_END();
566 
567 	/* Mark reachable instruction without side effects as dead */
568 	int b = ssa->cfg.blocks_count;
569 	while (b > 0) {
570 		int	op_data = -1;
571 
572 		b--;
573 		zend_basic_block *block = &ssa->cfg.blocks[b];
574 		if (!(block->flags & ZEND_BB_REACHABLE)) {
575 			continue;
576 		}
577 		i = block->start + block->len;
578 		while (i > block->start) {
579 			i--;
580 
581 			if (op_array->opcodes[i].opcode == ZEND_OP_DATA) {
582 				op_data = i;
583 				continue;
584 			}
585 
586 			if (zend_bitset_in(ctx.instr_worklist, i)) {
587 				zend_bitset_excl(ctx.instr_worklist, i);
588 				add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], ssa, 0);
589 				if (op_data >= 0) {
590 					add_operands_to_worklists(&ctx, &op_array->opcodes[op_data], &ssa->ops[op_data], ssa, 0);
591 				}
592 			} else if (may_have_side_effects(op_array, ssa, &op_array->opcodes[i], &ssa->ops[i], ctx.reorder_dtor_effects)
593 					|| (zend_may_throw(&op_array->opcodes[i], &ssa->ops[i], op_array, ssa)
594 						&& !may_throw_dce_exception(&op_array->opcodes[i]))
595 					|| (has_varargs && may_break_varargs(op_array, ssa, &ssa->ops[i]))) {
596 				if (op_array->opcodes[i].opcode == ZEND_NEW
597 						&& op_array->opcodes[i+1].opcode == ZEND_DO_FCALL
598 						&& ssa->ops[i].result_def >= 0
599 						&& ssa->vars[ssa->ops[i].result_def].escape_state == ESCAPE_STATE_NO_ESCAPE) {
600 					zend_bitset_incl(ctx.instr_dead, i);
601 					zend_bitset_incl(ctx.instr_dead, i+1);
602 				} else {
603 					add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], ssa, 0);
604 					if (op_data >= 0) {
605 						add_operands_to_worklists(&ctx, &op_array->opcodes[op_data], &ssa->ops[op_data], ssa, 0);
606 					}
607 				}
608 			} else {
609 				zend_bitset_incl(ctx.instr_dead, i);
610 				if (op_data >= 0) {
611 					zend_bitset_incl(ctx.instr_dead, op_data);
612 				}
613 			}
614 			op_data = -1;
615 		}
616 	}
617 
618 	/* Propagate liveness backwards to all definitions of used vars */
619 	while (!zend_bitset_empty(ctx.instr_worklist, ctx.instr_worklist_len)
620 			|| !zend_bitset_empty(ctx.phi_worklist, ctx.phi_worklist_len)) {
621 		while ((i = zend_bitset_pop_first(ctx.instr_worklist, ctx.instr_worklist_len)) >= 0) {
622 			zend_bitset_excl(ctx.instr_dead, i);
623 			add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], ssa, 1);
624 			if (i < op_array->last
625 			 && (op_array->opcodes[i+1].opcode == ZEND_OP_DATA
626 			  || (op_array->opcodes[i].opcode == ZEND_NEW
627 			   && op_array->opcodes[i+1].opcode == ZEND_DO_FCALL))) {
628 				zend_bitset_excl(ctx.instr_dead, i+1);
629 				add_operands_to_worklists(&ctx, &op_array->opcodes[i+1], &ssa->ops[i+1], ssa, 1);
630 			}
631 		}
632 		while ((i = zend_bitset_pop_first(ctx.phi_worklist, ctx.phi_worklist_len)) >= 0) {
633 			zend_bitset_excl(ctx.phi_dead, i);
634 			zend_bitset_excl(ctx.phi_worklist_no_val, i);
635 			add_phi_sources_to_worklists(&ctx, ssa->vars[i].definition_phi, 1);
636 		}
637 	}
638 
639 	/* Eliminate dead instructions */
640 	ZEND_BITSET_FOREACH(ctx.instr_dead, ctx.instr_worklist_len, i) {
641 		removed_ops += dce_instr(&ctx, &op_array->opcodes[i], &ssa->ops[i]);
642 	} ZEND_BITSET_FOREACH_END();
643 
644 	/* Improper uses don't count as "uses" for the purpose of instruction elimination,
645 	 * but we have to retain phis defining them.
646 	 * Propagate this information backwards, marking any phi with an improperly used
647 	 * target as non-dead. */
648 	while ((i = zend_bitset_pop_first(ctx.phi_worklist_no_val, ctx.phi_worklist_len)) >= 0) {
649 		zend_ssa_phi *phi = ssa->vars[i].definition_phi;
650 		int source;
651 		zend_bitset_excl(ctx.phi_dead, i);
652 		FOREACH_PHI_SOURCE(phi, source) {
653 			add_to_phi_worklist_no_val(&ctx, source);
654 		} FOREACH_PHI_SOURCE_END();
655 	}
656 
657 	/* Now collect the actually dead phis */
658 	FOREACH_PHI(phi) {
659 		if (zend_bitset_in(ctx.phi_dead, phi->ssa_var)) {
660 			zend_ssa_remove_uses_of_var(ssa, phi->ssa_var);
661 			zend_ssa_remove_phi(ssa, phi);
662 		} else {
663 			/* Remove trivial phis (phis with identical source operands) */
664 			try_remove_trivial_phi(&ctx, phi);
665 		}
666 	} FOREACH_PHI_END();
667 
668 	return removed_ops;
669 }
670