1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine, DCE - Dead Code Elimination |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2018 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 +----------------------------------------------------------------------+
17 */
18
19 #include "ZendAccelerator.h"
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_effect() 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 */
46
47 typedef struct {
48 zend_ssa *ssa;
49 zend_op_array *op_array;
50 zend_bitset instr_dead;
51 zend_bitset phi_dead;
52 zend_bitset instr_worklist;
53 zend_bitset phi_worklist;
54 zend_bitset phi_worklist_no_val;
55 uint32_t instr_worklist_len;
56 uint32_t phi_worklist_len;
57 unsigned reorder_dtor_effects : 1;
58 } context;
59
is_bad_mod(const zend_ssa * ssa,int use,int def)60 static inline zend_bool is_bad_mod(const zend_ssa *ssa, int use, int def) {
61 if (def < 0) {
62 /* This modification is not tracked by SSA, assume the worst */
63 return 1;
64 }
65 if (ssa->var_info[use].type & MAY_BE_REF) {
66 /* Modification of reference may have side-effect */
67 return 1;
68 }
69 return 0;
70 }
71
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)72 static inline zend_bool may_have_side_effects(
73 zend_op_array *op_array, zend_ssa *ssa,
74 const zend_op *opline, const zend_ssa_op *ssa_op,
75 zend_bool reorder_dtor_effects) {
76 switch (opline->opcode) {
77 case ZEND_NOP:
78 case ZEND_IS_IDENTICAL:
79 case ZEND_IS_NOT_IDENTICAL:
80 case ZEND_QM_ASSIGN:
81 case ZEND_FREE:
82 case ZEND_TYPE_CHECK:
83 case ZEND_DEFINED:
84 case ZEND_ADD:
85 case ZEND_SUB:
86 case ZEND_MUL:
87 case ZEND_POW:
88 case ZEND_BW_OR:
89 case ZEND_BW_AND:
90 case ZEND_BW_XOR:
91 case ZEND_CONCAT:
92 case ZEND_FAST_CONCAT:
93 case ZEND_DIV:
94 case ZEND_MOD:
95 case ZEND_BOOL_XOR:
96 case ZEND_BOOL:
97 case ZEND_BOOL_NOT:
98 case ZEND_BW_NOT:
99 case ZEND_SL:
100 case ZEND_SR:
101 case ZEND_IS_EQUAL:
102 case ZEND_IS_NOT_EQUAL:
103 case ZEND_IS_SMALLER:
104 case ZEND_IS_SMALLER_OR_EQUAL:
105 case ZEND_CASE:
106 case ZEND_CAST:
107 case ZEND_ROPE_INIT:
108 case ZEND_ROPE_ADD:
109 case ZEND_ROPE_END:
110 case ZEND_INIT_ARRAY:
111 case ZEND_ADD_ARRAY_ELEMENT:
112 case ZEND_SPACESHIP:
113 case ZEND_STRLEN:
114 case ZEND_COUNT:
115 case ZEND_GET_TYPE:
116 case ZEND_ISSET_ISEMPTY_THIS:
117 case ZEND_ISSET_ISEMPTY_DIM_OBJ:
118 case ZEND_FETCH_DIM_IS:
119 case ZEND_ISSET_ISEMPTY_CV:
120 case ZEND_ISSET_ISEMPTY_VAR:
121 case ZEND_FETCH_IS:
122 case ZEND_IN_ARRAY:
123 /* No side effects */
124 return 0;
125 case ZEND_JMP:
126 case ZEND_JMPZ:
127 case ZEND_JMPNZ:
128 case ZEND_JMPZNZ:
129 case ZEND_JMPZ_EX:
130 case ZEND_JMPNZ_EX:
131 case ZEND_JMP_SET:
132 case ZEND_COALESCE:
133 case ZEND_ASSERT_CHECK:
134 /* For our purposes a jumps and branches are side effects. */
135 return 1;
136 case ZEND_BEGIN_SILENCE:
137 case ZEND_END_SILENCE:
138 case ZEND_ECHO:
139 case ZEND_INCLUDE_OR_EVAL:
140 case ZEND_THROW:
141 case ZEND_EXT_STMT:
142 case ZEND_EXT_FCALL_BEGIN:
143 case ZEND_EXT_FCALL_END:
144 case ZEND_EXT_NOP:
145 case ZEND_TICKS:
146 case ZEND_YIELD:
147 case ZEND_YIELD_FROM:
148 /* Intrinsic side effects */
149 return 1;
150 case ZEND_DO_FCALL:
151 case ZEND_DO_FCALL_BY_NAME:
152 case ZEND_DO_ICALL:
153 case ZEND_DO_UCALL:
154 /* For now assume all calls have side effects */
155 return 1;
156 case ZEND_RECV:
157 case ZEND_RECV_INIT:
158 /* Even though RECV_INIT can be side-effect free, these cannot be simply dropped
159 * due to the prologue skipping code. */
160 return 1;
161 case ZEND_ASSIGN_REF:
162 return 1;
163 case ZEND_ASSIGN:
164 {
165 if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)) {
166 return 1;
167 }
168 if (!reorder_dtor_effects) {
169 if (opline->op2_type != IS_CONST && (OP2_INFO() & MAY_HAVE_DTOR)) {
170 /* DCE might shorten lifetime */
171 return 1;
172 }
173 }
174 return 0;
175 }
176 case ZEND_UNSET_VAR:
177 return 1;
178 case ZEND_UNSET_CV:
179 {
180 uint32_t t1 = OP1_INFO();
181 if (t1 & MAY_BE_REF) {
182 /* We don't consider uses as the LHS of an assignment as real uses during DCE, so
183 * an unset may be considered dead even if there is a later assignment to the
184 * variable. Removing the unset in this case would not be correct if the variable
185 * is a reference, because unset breaks references. */
186 return 1;
187 }
188 return 0;
189 }
190 case ZEND_PRE_INC:
191 case ZEND_POST_INC:
192 case ZEND_PRE_DEC:
193 case ZEND_POST_DEC:
194 return is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def);
195 case ZEND_ASSIGN_ADD:
196 case ZEND_ASSIGN_SUB:
197 case ZEND_ASSIGN_MUL:
198 case ZEND_ASSIGN_DIV:
199 case ZEND_ASSIGN_MOD:
200 case ZEND_ASSIGN_SL:
201 case ZEND_ASSIGN_SR:
202 case ZEND_ASSIGN_CONCAT:
203 case ZEND_ASSIGN_BW_OR:
204 case ZEND_ASSIGN_BW_AND:
205 case ZEND_ASSIGN_BW_XOR:
206 case ZEND_ASSIGN_POW:
207 if (opline->extended_value) {
208 /* ASSIGN_DIM has no side-effect, but we can't deal with OP_DATA anyway */
209 return 1;
210 }
211 return is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def);
212 default:
213 /* For everything we didn't handle, assume a side-effect */
214 return 1;
215 }
216 }
217
add_to_worklists(context * ctx,int var_num,int check)218 static zend_always_inline void add_to_worklists(context *ctx, int var_num, int check) {
219 zend_ssa_var *var = &ctx->ssa->vars[var_num];
220 if (var->definition >= 0) {
221 if (!check || zend_bitset_in(ctx->instr_dead, var->definition)) {
222 zend_bitset_incl(ctx->instr_worklist, var->definition);
223 }
224 } else if (var->definition_phi) {
225 if (!check || zend_bitset_in(ctx->phi_dead, var_num)) {
226 zend_bitset_incl(ctx->phi_worklist, var_num);
227 }
228 }
229 }
230
add_to_phi_worklist_no_val(context * ctx,int var_num)231 static inline void add_to_phi_worklist_no_val(context *ctx, int var_num) {
232 zend_ssa_var *var = &ctx->ssa->vars[var_num];
233 if (var->definition_phi && zend_bitset_in(ctx->phi_dead, var_num)) {
234 zend_bitset_incl(ctx->phi_worklist_no_val, var_num);
235 }
236 }
237
add_operands_to_worklists(context * ctx,zend_op * opline,zend_ssa_op * ssa_op,int check)238 static zend_always_inline void add_operands_to_worklists(context *ctx, zend_op *opline, zend_ssa_op *ssa_op, int check) {
239 if (ssa_op->result_use >= 0) {
240 add_to_worklists(ctx, ssa_op->result_use, check);
241 }
242 if (ssa_op->op1_use >= 0) {
243 if (!zend_ssa_is_no_val_use(opline, ssa_op, ssa_op->op1_use)) {
244 add_to_worklists(ctx, ssa_op->op1_use, check);
245 } else {
246 add_to_phi_worklist_no_val(ctx, ssa_op->op1_use);
247 }
248 }
249 if (ssa_op->op2_use >= 0) {
250 if (!zend_ssa_is_no_val_use(opline, ssa_op, ssa_op->op2_use)) {
251 add_to_worklists(ctx, ssa_op->op2_use, check);
252 } else {
253 add_to_phi_worklist_no_val(ctx, ssa_op->op2_use);
254 }
255 }
256 }
257
add_phi_sources_to_worklists(context * ctx,zend_ssa_phi * phi,int check)258 static zend_always_inline void add_phi_sources_to_worklists(context *ctx, zend_ssa_phi *phi, int check) {
259 zend_ssa *ssa = ctx->ssa;
260 int source;
261 FOREACH_PHI_SOURCE(phi, source) {
262 add_to_worklists(ctx, source, check);
263 } FOREACH_PHI_SOURCE_END();
264 }
265
is_var_dead(context * ctx,int var_num)266 static inline zend_bool is_var_dead(context *ctx, int var_num) {
267 zend_ssa_var *var = &ctx->ssa->vars[var_num];
268 if (var->definition_phi) {
269 return zend_bitset_in(ctx->phi_dead, var_num);
270 } else if (var->definition >= 0) {
271 return zend_bitset_in(ctx->instr_dead, var->definition);
272 } else {
273 /* Variable has no definition, so either the definition has already been removed (var is
274 * dead) or this is one of the implicit variables at the start of the function (for our
275 * purposes live) */
276 return var_num >= ctx->op_array->last_var;
277 }
278 }
279
280 // Sometimes we can mark the var as EXT_UNUSED
try_remove_var_def(context * ctx,int free_var,int use_chain,zend_op * opline)281 static zend_bool try_remove_var_def(context *ctx, int free_var, int use_chain, zend_op *opline) {
282 if (use_chain >= 0) {
283 return 0;
284 }
285 zend_ssa_var *var = &ctx->ssa->vars[free_var];
286 int def = var->definition;
287
288 if (def >= 0) {
289 zend_ssa_op *def_op = &ctx->ssa->ops[def];
290
291 if (def_op->result_def == free_var
292 && var->phi_use_chain == NULL
293 && var->use_chain == (opline - ctx->op_array->opcodes)) {
294 zend_op *def_opline = &ctx->op_array->opcodes[def];
295
296 switch (def_opline->opcode) {
297 case ZEND_ASSIGN:
298 case ZEND_ASSIGN_REF:
299 case ZEND_ASSIGN_DIM:
300 case ZEND_ASSIGN_OBJ:
301 case ZEND_ASSIGN_ADD:
302 case ZEND_ASSIGN_SUB:
303 case ZEND_ASSIGN_MUL:
304 case ZEND_ASSIGN_DIV:
305 case ZEND_ASSIGN_MOD:
306 case ZEND_ASSIGN_SL:
307 case ZEND_ASSIGN_SR:
308 case ZEND_ASSIGN_CONCAT:
309 case ZEND_ASSIGN_BW_OR:
310 case ZEND_ASSIGN_BW_AND:
311 case ZEND_ASSIGN_BW_XOR:
312 case ZEND_ASSIGN_POW:
313 case ZEND_PRE_INC:
314 case ZEND_PRE_DEC:
315 case ZEND_PRE_INC_OBJ:
316 case ZEND_POST_INC_OBJ:
317 case ZEND_PRE_DEC_OBJ:
318 case ZEND_POST_DEC_OBJ:
319 case ZEND_DO_ICALL:
320 case ZEND_DO_UCALL:
321 case ZEND_DO_FCALL_BY_NAME:
322 case ZEND_DO_FCALL:
323 case ZEND_INCLUDE_OR_EVAL:
324 case ZEND_YIELD:
325 case ZEND_YIELD_FROM:
326 case ZEND_ASSERT_CHECK:
327 def_opline->result_type = IS_UNUSED;
328 def_opline->result.var = 0;
329 def_op->result_def = -1;
330 var->definition = -1;
331 return 1;
332 default:
333 break;
334 }
335 }
336 }
337 return 0;
338 }
339
340 /* Returns whether the instruction has been DCEd */
dce_instr(context * ctx,zend_op * opline,zend_ssa_op * ssa_op)341 static zend_bool dce_instr(context *ctx, zend_op *opline, zend_ssa_op *ssa_op) {
342 zend_ssa *ssa = ctx->ssa;
343 int free_var = -1;
344 zend_uchar free_var_type;
345
346 if (opline->opcode == ZEND_NOP) {
347 return 0;
348 }
349
350 /* We mark FREEs as dead, but they're only really dead if the destroyed var is dead */
351 if (opline->opcode == ZEND_FREE
352 && (ssa->var_info[ssa_op->op1_use].type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF))
353 && !is_var_dead(ctx, ssa_op->op1_use)) {
354 return 0;
355 }
356
357 if ((opline->op1_type & (IS_VAR|IS_TMP_VAR))&& !is_var_dead(ctx, ssa_op->op1_use)) {
358 if (!try_remove_var_def(ctx, ssa_op->op1_use, ssa_op->op1_use_chain, opline)) {
359 if (ssa->var_info[ssa_op->op1_use].type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF)
360 && opline->opcode != ZEND_CASE) {
361 free_var = ssa_op->op1_use;
362 free_var_type = opline->op1_type;
363 }
364 }
365 }
366 if ((opline->op2_type & (IS_VAR|IS_TMP_VAR)) && !is_var_dead(ctx, ssa_op->op2_use)) {
367 if (!try_remove_var_def(ctx, ssa_op->op2_use, ssa_op->op2_use_chain, opline)) {
368 if (ssa->var_info[ssa_op->op2_use].type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF)) {
369 if (free_var >= 0) {
370 // TODO: We can't free two vars. Keep instruction alive.
371 zend_bitset_excl(ctx->instr_dead, opline - ctx->op_array->opcodes);
372 return 0;
373 }
374 free_var = ssa_op->op2_use;
375 free_var_type = opline->op2_type;
376 }
377 }
378 }
379
380 zend_ssa_rename_defs_of_instr(ctx->ssa, ssa_op);
381 zend_ssa_remove_instr(ctx->ssa, opline, ssa_op);
382
383 if (free_var >= 0) {
384 opline->opcode = ZEND_FREE;
385 opline->op1.var = (uintptr_t) ZEND_CALL_VAR_NUM(NULL, ssa->vars[free_var].var);
386 opline->op1_type = free_var_type;
387
388 ssa_op->op1_use = free_var;
389 ssa_op->op1_use_chain = ssa->vars[free_var].use_chain;
390 ssa->vars[free_var].use_chain = ssa_op - ssa->ops;
391 return 0;
392 }
393 return 1;
394 }
395
396 // TODO Move this somewhere else (CFG simplification?)
simplify_jumps(zend_ssa * ssa,zend_op_array * op_array)397 static int simplify_jumps(zend_ssa *ssa, zend_op_array *op_array) {
398 int removed_ops = 0;
399 zend_basic_block *block;
400 FOREACH_BLOCK(block) {
401 int block_num = block - ssa->cfg.blocks;
402 zend_op *opline = &op_array->opcodes[block->start + block->len - 1];
403 zend_ssa_op *ssa_op = &ssa->ops[block->start + block->len - 1];
404 zval *op1;
405
406 if (block->len == 0) {
407 continue;
408 }
409
410 /* Convert jump-and-set into jump if result is not used */
411 switch (opline->opcode) {
412 case ZEND_JMPZ_EX:
413 ZEND_ASSERT(ssa_op->result_def >= 0);
414 if (ssa->vars[ssa_op->result_def].use_chain < 0
415 && ssa->vars[ssa_op->result_def].phi_use_chain == NULL) {
416 opline->opcode = ZEND_JMPZ;
417 opline->result_type = IS_UNUSED;
418 zend_ssa_remove_result_def(ssa, ssa_op);
419 }
420 break;
421 case ZEND_JMPNZ_EX:
422 case ZEND_JMP_SET:
423 ZEND_ASSERT(ssa_op->result_def >= 0);
424 if (ssa->vars[ssa_op->result_def].use_chain < 0
425 && ssa->vars[ssa_op->result_def].phi_use_chain == NULL) {
426 opline->opcode = ZEND_JMPNZ;
427 opline->result_type = IS_UNUSED;
428 zend_ssa_remove_result_def(ssa, ssa_op);
429 }
430 break;
431 }
432
433 /* Convert jump-and-set to QM_ASSIGN/BOOL if the "else" branch is not taken. */
434 switch (opline->opcode) {
435 case ZEND_JMPZ_EX:
436 case ZEND_JMPNZ_EX:
437 if (block->successors_count == 1 && block->successors[0] != block_num + 1) {
438 opline->opcode = ZEND_BOOL;
439 }
440 break;
441 case ZEND_JMP_SET:
442 case ZEND_COALESCE:
443 if (block->successors_count == 1 && block->successors[0] != block_num + 1) {
444 opline->opcode = ZEND_QM_ASSIGN;
445 }
446 break;
447 }
448
449 if (opline->op1_type != IS_CONST) {
450 continue;
451 }
452
453 /* Convert constant conditional jump to unconditional jump */
454 op1 = &ZEND_OP1_LITERAL(opline);
455 switch (opline->opcode) {
456 case ZEND_JMPZ:
457 if (!zend_is_true(op1)) {
458 literal_dtor(op1);
459 opline->op1_type = IS_UNUSED;
460 opline->op1.num = opline->op2.num;
461 opline->opcode = ZEND_JMP;
462 } else {
463 MAKE_NOP(opline);
464 removed_ops++;
465 }
466 break;
467 case ZEND_JMPNZ:
468 if (zend_is_true(op1)) {
469 literal_dtor(op1);
470 opline->op1_type = IS_UNUSED;
471 opline->op1.num = opline->op2.num;
472 opline->opcode = ZEND_JMP;
473 } else {
474 MAKE_NOP(opline);
475 removed_ops++;
476 }
477 break;
478 case ZEND_COALESCE:
479 ZEND_ASSERT(ssa_op->result_def >= 0);
480 if (ssa->vars[ssa_op->result_def].use_chain >= 0
481 || ssa->vars[ssa_op->result_def].phi_use_chain != NULL) {
482 break;
483 }
484
485 zend_ssa_remove_result_def(ssa, ssa_op);
486 if (Z_TYPE_P(op1) != IS_NULL) {
487 literal_dtor(op1);
488 opline->op1_type = IS_UNUSED;
489 opline->op1.num = opline->op2.num;
490 opline->opcode = ZEND_JMP;
491 opline->result_type = IS_UNUSED;
492 } else {
493 MAKE_NOP(opline);
494 removed_ops++;
495 }
496 break;
497 }
498 } FOREACH_BLOCK_END();
499 return removed_ops;
500 }
501
get_common_phi_source(zend_ssa * ssa,zend_ssa_phi * phi)502 static inline int get_common_phi_source(zend_ssa *ssa, zend_ssa_phi *phi) {
503 int common_source = -1;
504 int source;
505 FOREACH_PHI_SOURCE(phi, source) {
506 if (common_source == -1) {
507 common_source = source;
508 } else if (common_source != source && source != phi->ssa_var) {
509 return -1;
510 }
511 } FOREACH_PHI_SOURCE_END();
512 ZEND_ASSERT(common_source != -1);
513 return common_source;
514 }
515
try_remove_trivial_phi(context * ctx,zend_ssa_phi * phi)516 static void try_remove_trivial_phi(context *ctx, zend_ssa_phi *phi) {
517 zend_ssa *ssa = ctx->ssa;
518 if (phi->pi < 0) {
519 /* Phi assignment with identical source operands */
520 int common_source = get_common_phi_source(ssa, phi);
521 if (common_source >= 0) {
522 zend_ssa_rename_var_uses(ssa, phi->ssa_var, common_source, 1);
523 zend_ssa_remove_phi(ssa, phi);
524 }
525 } else {
526 /* Pi assignment that is only used in Phi/Pi assignments */
527 // TODO What if we want to rerun type inference after DCE? Maybe separate this?
528 /*ZEND_ASSERT(phi->sources[0] != -1);
529 if (ssa->vars[phi->ssa_var].use_chain < 0) {
530 zend_ssa_rename_var_uses_keep_types(ssa, phi->ssa_var, phi->sources[0], 1);
531 zend_ssa_remove_phi(ssa, phi);
532 }*/
533 }
534 }
535
may_break_varargs(const zend_op_array * op_array,const zend_ssa * ssa,const zend_ssa_op * ssa_op)536 static inline zend_bool may_break_varargs(const zend_op_array *op_array, const zend_ssa *ssa, const zend_ssa_op *ssa_op) {
537 if (ssa_op->op1_def >= 0
538 && ssa->vars[ssa_op->op1_def].var < op_array->num_args) {
539 return 1;
540 }
541 if (ssa_op->op2_def >= 0
542 && ssa->vars[ssa_op->op2_def].var < op_array->num_args) {
543 return 1;
544 }
545 if (ssa_op->result_def >= 0
546 && ssa->vars[ssa_op->result_def].var < op_array->num_args) {
547 return 1;
548 }
549 return 0;
550 }
551
dce_live_ranges(context * ctx,zend_op_array * op_array,zend_ssa * ssa)552 static void dce_live_ranges(context *ctx, zend_op_array *op_array, zend_ssa *ssa)
553 {
554 int i = 0;
555 int j = 0;
556 zend_live_range *live_range = op_array->live_range;
557
558 while (i < op_array->last_live_range) {
559 if ((live_range->var & ZEND_LIVE_MASK) != ZEND_LIVE_TMPVAR) {
560 /* keep */
561 j++;
562 } else {
563 uint32_t var = live_range->var & ~ZEND_LIVE_MASK;
564 uint32_t def = live_range->start - 1;
565
566 if ((op_array->opcodes[def].result_type == IS_UNUSED) &&
567 (UNEXPECTED(op_array->opcodes[def].opcode == ZEND_EXT_STMT) ||
568 UNEXPECTED(op_array->opcodes[def].opcode == ZEND_EXT_FCALL_END) ||
569 UNEXPECTED(op_array->opcodes[def].opcode == ZEND_END_SILENCE))) {
570 def--;
571 }
572
573 if (op_array->opcodes[def].result_type == IS_UNUSED) {
574 if (op_array->opcodes[def].opcode == ZEND_DO_FCALL) {
575 /* constructor call */
576 do {
577 def--;
578 if ((op_array->opcodes[def].result_type & (IS_TMP_VAR|IS_VAR))
579 && op_array->opcodes[def].result.var == var) {
580 ZEND_ASSERT(op_array->opcodes[def].opcode == ZEND_NEW);
581 break;
582 }
583 } while (def > 0);
584 } else if (op_array->opcodes[def].opcode == ZEND_OP_DATA) {
585 def--;
586 }
587 }
588
589 #if ZEND_DEBUG
590 ZEND_ASSERT(op_array->opcodes[def].result_type & (IS_TMP_VAR|IS_VAR));
591 ZEND_ASSERT(op_array->opcodes[def].result.var == var);
592 ZEND_ASSERT(ssa->ops[def].result_def >= 0);
593 #else
594 if (!(op_array->opcodes[def].result_type & (IS_TMP_VAR|IS_VAR))
595 || op_array->opcodes[def].result.var != var
596 || ssa->ops[def].result_def < 0) {
597 /* TODO: Some wrong live-range? keep it. */
598 j++;
599 live_range++;
600 i++;
601 continue;
602 }
603 #endif
604
605 var = ssa->ops[def].result_def;
606
607 if ((ssa->var_info[var].type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF))
608 && !is_var_dead(ctx, var)) {
609 /* keep */
610 j++;
611 } else if (i != j) {
612 op_array->live_range[j] = *live_range;
613 }
614 }
615
616 live_range++;
617 i++;
618 }
619 op_array->last_live_range = j;
620 if (op_array->last_live_range == 0) {
621 efree(op_array->live_range);
622 op_array->live_range = NULL;
623 }
624 }
625
dce_optimize_op_array(zend_op_array * op_array,zend_ssa * ssa,zend_bool reorder_dtor_effects)626 int dce_optimize_op_array(zend_op_array *op_array, zend_ssa *ssa, zend_bool reorder_dtor_effects) {
627 int i;
628 zend_ssa_phi *phi;
629 int removed_ops = 0;
630
631 /* DCE of CV operations that changes arguments may affect vararg functions. */
632 zend_bool has_varargs = ssa->cfg.vararg;
633
634 context ctx;
635 ctx.ssa = ssa;
636 ctx.op_array = op_array;
637 ctx.reorder_dtor_effects = reorder_dtor_effects;
638
639 /* We have no dedicated phi vector, so we use the whole ssa var vector instead */
640 ctx.instr_worklist_len = zend_bitset_len(op_array->last);
641 ctx.instr_worklist = alloca(sizeof(zend_ulong) * ctx.instr_worklist_len);
642 memset(ctx.instr_worklist, 0, sizeof(zend_ulong) * ctx.instr_worklist_len);
643 ctx.phi_worklist_len = zend_bitset_len(ssa->vars_count);
644 ctx.phi_worklist = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len);
645 memset(ctx.phi_worklist, 0, sizeof(zend_ulong) * ctx.phi_worklist_len);
646 ctx.phi_worklist_no_val = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len);
647 memset(ctx.phi_worklist_no_val, 0, sizeof(zend_ulong) * ctx.phi_worklist_len);
648
649 /* Optimistically assume all instructions and phis to be dead */
650 ctx.instr_dead = alloca(sizeof(zend_ulong) * ctx.instr_worklist_len);
651 memset(ctx.instr_dead, 0, sizeof(zend_ulong) * ctx.instr_worklist_len);
652 ctx.phi_dead = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len);
653 memset(ctx.phi_dead, 0xff, sizeof(zend_ulong) * ctx.phi_worklist_len);
654
655 /* Mark reacable instruction without side effects as dead */
656 int b = ssa->cfg.blocks_count;
657 while (b > 0) {
658 b--;
659 zend_basic_block *block = &ssa->cfg.blocks[b];
660 if (!(block->flags & ZEND_BB_REACHABLE)) {
661 continue;
662 }
663 i = block->start + block->len;
664 while (i > block->start) {
665 i--;
666
667 if (zend_bitset_in(ctx.instr_worklist, i)) {
668 zend_bitset_excl(ctx.instr_worklist, i);
669 add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], 0);
670 } else if (may_have_side_effects(op_array, ssa, &op_array->opcodes[i], &ssa->ops[i], ctx.reorder_dtor_effects)
671 || zend_may_throw(&op_array->opcodes[i], op_array, ssa)
672 || (has_varargs && may_break_varargs(op_array, ssa, &ssa->ops[i]))) {
673 add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], 0);
674 } else {
675 zend_bitset_incl(ctx.instr_dead, i);
676 }
677
678 }
679 }
680
681 /* Propagate liveness backwards to all definitions of used vars */
682 while (!zend_bitset_empty(ctx.instr_worklist, ctx.instr_worklist_len)
683 || !zend_bitset_empty(ctx.phi_worklist, ctx.phi_worklist_len)) {
684 while ((i = zend_bitset_pop_first(ctx.instr_worklist, ctx.instr_worklist_len)) >= 0) {
685 zend_bitset_excl(ctx.instr_dead, i);
686 add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], 1);
687 }
688 while ((i = zend_bitset_pop_first(ctx.phi_worklist, ctx.phi_worklist_len)) >= 0) {
689 zend_bitset_excl(ctx.phi_dead, i);
690 zend_bitset_excl(ctx.phi_worklist_no_val, i);
691 add_phi_sources_to_worklists(&ctx, ssa->vars[i].definition_phi, 1);
692 }
693 }
694
695 if (op_array->live_range) {
696 dce_live_ranges(&ctx, op_array, ssa);
697 }
698
699 /* Eliminate dead instructions */
700 ZEND_BITSET_FOREACH(ctx.instr_dead, ctx.instr_worklist_len, i) {
701 removed_ops += dce_instr(&ctx, &op_array->opcodes[i], &ssa->ops[i]);
702 } ZEND_BITSET_FOREACH_END();
703
704 /* Improper uses don't count as "uses" for the purpose of instruction elimination,
705 * but we have to retain phis defining them.
706 * Propagate this information backwards, marking any phi with an improperly used
707 * target as non-dead. */
708 while ((i = zend_bitset_pop_first(ctx.phi_worklist_no_val, ctx.phi_worklist_len)) >= 0) {
709 zend_ssa_phi *phi = ssa->vars[i].definition_phi;
710 int source;
711 zend_bitset_excl(ctx.phi_dead, i);
712 FOREACH_PHI_SOURCE(phi, source) {
713 add_to_phi_worklist_no_val(&ctx, source);
714 } FOREACH_PHI_SOURCE_END();
715 }
716
717 /* Now collect the actually dead phis */
718 FOREACH_PHI(phi) {
719 if (zend_bitset_in(ctx.phi_dead, phi->ssa_var)) {
720 zend_ssa_remove_uses_of_var(ssa, phi->ssa_var);
721 zend_ssa_remove_phi(ssa, phi);
722 } else {
723 /* Remove trivial phis (phis with identical source operands) */
724 try_remove_trivial_phi(&ctx, phi);
725 }
726 } FOREACH_PHI_END();
727
728 removed_ops += simplify_jumps(ssa, op_array);
729
730 return removed_ops;
731 }
732
