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