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
