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 | 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 optmization, 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_ADD:
205 case ZEND_ASSIGN_SUB:
206 case ZEND_ASSIGN_MUL:
207 case ZEND_ASSIGN_DIV:
208 case ZEND_ASSIGN_MOD:
209 case ZEND_ASSIGN_SL:
210 case ZEND_ASSIGN_SR:
211 case ZEND_ASSIGN_CONCAT:
212 case ZEND_ASSIGN_BW_OR:
213 case ZEND_ASSIGN_BW_AND:
214 case ZEND_ASSIGN_BW_XOR:
215 case ZEND_ASSIGN_POW:
216 return is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)
217 || (opline->extended_value
218 && ssa->vars[ssa_op->op1_def].escape_state != ESCAPE_STATE_NO_ESCAPE);
219 case ZEND_ASSIGN_DIM:
220 case ZEND_ASSIGN_OBJ:
221 if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)
222 || ssa->vars[ssa_op->op1_def].escape_state != ESCAPE_STATE_NO_ESCAPE) {
223 return 1;
224 }
225 if (!reorder_dtor_effects) {
226 opline++;
227 ssa_op++;
228 if (opline->op1_type != IS_CONST
229 && (OP1_INFO() & MAY_HAVE_DTOR)) {
230 /* DCE might shorten lifetime */
231 return 1;
232 }
233 }
234 return 0;
235 case ZEND_PRE_INC_OBJ:
236 case ZEND_PRE_DEC_OBJ:
237 case ZEND_POST_INC_OBJ:
238 case ZEND_POST_DEC_OBJ:
239 if (is_bad_mod(ssa, ssa_op->op1_use, ssa_op->op1_def)
240 || ssa->vars[ssa_op->op1_def].escape_state != ESCAPE_STATE_NO_ESCAPE) {
241 return 1;
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,int check)270 static zend_always_inline void add_operands_to_worklists(context *ctx, zend_op *opline, zend_ssa_op *ssa_op, 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 add_to_worklists(ctx, ssa_op->op1_use, check);
277 } else {
278 add_to_phi_worklist_no_val(ctx, ssa_op->op1_use);
279 }
280 }
281 if (ssa_op->op2_use >= 0) {
282 if (!zend_ssa_is_no_val_use(opline, ssa_op, ssa_op->op2_use)) {
283 add_to_worklists(ctx, ssa_op->op2_use, check);
284 } else {
285 add_to_phi_worklist_no_val(ctx, ssa_op->op2_use);
286 }
287 }
288 }
289
add_phi_sources_to_worklists(context * ctx,zend_ssa_phi * phi,int check)290 static zend_always_inline void add_phi_sources_to_worklists(context *ctx, zend_ssa_phi *phi, int check) {
291 zend_ssa *ssa = ctx->ssa;
292 int source;
293 FOREACH_PHI_SOURCE(phi, source) {
294 add_to_worklists(ctx, source, check);
295 } FOREACH_PHI_SOURCE_END();
296 }
297
is_var_dead(context * ctx,int var_num)298 static inline zend_bool is_var_dead(context *ctx, int var_num) {
299 zend_ssa_var *var = &ctx->ssa->vars[var_num];
300 if (var->definition_phi) {
301 return zend_bitset_in(ctx->phi_dead, var_num);
302 } else if (var->definition >= 0) {
303 return zend_bitset_in(ctx->instr_dead, var->definition);
304 } else {
305 /* Variable has no definition, so either the definition has already been removed (var is
306 * dead) or this is one of the implicit variables at the start of the function (for our
307 * purposes live) */
308 return var_num >= ctx->op_array->last_var;
309 }
310 }
311
312 // Sometimes we can mark the var as EXT_UNUSED
try_remove_var_def(context * ctx,int free_var,int use_chain,zend_op * opline)313 static zend_bool try_remove_var_def(context *ctx, int free_var, int use_chain, zend_op *opline) {
314 if (use_chain >= 0) {
315 return 0;
316 }
317 zend_ssa_var *var = &ctx->ssa->vars[free_var];
318 int def = var->definition;
319
320 if (def >= 0) {
321 zend_ssa_op *def_op = &ctx->ssa->ops[def];
322
323 if (def_op->result_def == free_var
324 && var->phi_use_chain == NULL
325 && var->use_chain == (opline - ctx->op_array->opcodes)) {
326 zend_op *def_opline = &ctx->op_array->opcodes[def];
327
328 switch (def_opline->opcode) {
329 case ZEND_ASSIGN:
330 case ZEND_ASSIGN_REF:
331 case ZEND_ASSIGN_DIM:
332 case ZEND_ASSIGN_OBJ:
333 case ZEND_ASSIGN_ADD:
334 case ZEND_ASSIGN_SUB:
335 case ZEND_ASSIGN_MUL:
336 case ZEND_ASSIGN_DIV:
337 case ZEND_ASSIGN_MOD:
338 case ZEND_ASSIGN_SL:
339 case ZEND_ASSIGN_SR:
340 case ZEND_ASSIGN_CONCAT:
341 case ZEND_ASSIGN_BW_OR:
342 case ZEND_ASSIGN_BW_AND:
343 case ZEND_ASSIGN_BW_XOR:
344 case ZEND_ASSIGN_POW:
345 case ZEND_PRE_INC:
346 case ZEND_PRE_DEC:
347 case ZEND_PRE_INC_OBJ:
348 case ZEND_POST_INC_OBJ:
349 case ZEND_PRE_DEC_OBJ:
350 case ZEND_POST_DEC_OBJ:
351 case ZEND_DO_ICALL:
352 case ZEND_DO_UCALL:
353 case ZEND_DO_FCALL_BY_NAME:
354 case ZEND_DO_FCALL:
355 case ZEND_INCLUDE_OR_EVAL:
356 case ZEND_YIELD:
357 case ZEND_YIELD_FROM:
358 case ZEND_ASSERT_CHECK:
359 def_opline->result_type = IS_UNUSED;
360 def_opline->result.var = 0;
361 def_op->result_def = -1;
362 var->definition = -1;
363 return 1;
364 default:
365 break;
366 }
367 }
368 }
369 return 0;
370 }
371
372 /* Returns whether the instruction has been DCEd */
dce_instr(context * ctx,zend_op * opline,zend_ssa_op * ssa_op)373 static zend_bool dce_instr(context *ctx, zend_op *opline, zend_ssa_op *ssa_op) {
374 zend_ssa *ssa = ctx->ssa;
375 int free_var = -1;
376 zend_uchar free_var_type;
377
378 if (opline->opcode == ZEND_NOP) {
379 return 0;
380 }
381
382 /* We mark FREEs as dead, but they're only really dead if the destroyed var is dead */
383 if (opline->opcode == ZEND_FREE
384 && (ssa->var_info[ssa_op->op1_use].type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF))
385 && !is_var_dead(ctx, ssa_op->op1_use)) {
386 return 0;
387 }
388
389 if ((opline->op1_type & (IS_VAR|IS_TMP_VAR))&& !is_var_dead(ctx, ssa_op->op1_use)) {
390 if (!try_remove_var_def(ctx, ssa_op->op1_use, ssa_op->op1_use_chain, opline)) {
391 if (ssa->var_info[ssa_op->op1_use].type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF)
392 && opline->opcode != ZEND_CASE) {
393 free_var = ssa_op->op1_use;
394 free_var_type = opline->op1_type;
395 }
396 }
397 }
398 if ((opline->op2_type & (IS_VAR|IS_TMP_VAR)) && !is_var_dead(ctx, ssa_op->op2_use)) {
399 if (!try_remove_var_def(ctx, ssa_op->op2_use, ssa_op->op2_use_chain, opline)) {
400 if (ssa->var_info[ssa_op->op2_use].type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF)) {
401 if (free_var >= 0) {
402 // TODO: We can't free two vars. Keep instruction alive.
403 zend_bitset_excl(ctx->instr_dead, opline - ctx->op_array->opcodes);
404 return 0;
405 }
406 free_var = ssa_op->op2_use;
407 free_var_type = opline->op2_type;
408 }
409 }
410 }
411
412 zend_ssa_rename_defs_of_instr(ctx->ssa, ssa_op);
413 zend_ssa_remove_instr(ctx->ssa, opline, ssa_op);
414
415 if (free_var >= 0) {
416 opline->opcode = ZEND_FREE;
417 opline->op1.var = (uintptr_t) ZEND_CALL_VAR_NUM(NULL, ssa->vars[free_var].var);
418 opline->op1_type = free_var_type;
419
420 ssa_op->op1_use = free_var;
421 ssa_op->op1_use_chain = ssa->vars[free_var].use_chain;
422 ssa->vars[free_var].use_chain = ssa_op - ssa->ops;
423 return 0;
424 }
425 return 1;
426 }
427
get_common_phi_source(zend_ssa * ssa,zend_ssa_phi * phi)428 static inline int get_common_phi_source(zend_ssa *ssa, zend_ssa_phi *phi) {
429 int common_source = -1;
430 int source;
431 FOREACH_PHI_SOURCE(phi, source) {
432 if (common_source == -1) {
433 common_source = source;
434 } else if (common_source != source && source != phi->ssa_var) {
435 return -1;
436 }
437 } FOREACH_PHI_SOURCE_END();
438 ZEND_ASSERT(common_source != -1);
439 return common_source;
440 }
441
try_remove_trivial_phi(context * ctx,zend_ssa_phi * phi)442 static void try_remove_trivial_phi(context *ctx, zend_ssa_phi *phi) {
443 zend_ssa *ssa = ctx->ssa;
444 if (phi->pi < 0) {
445 /* Phi assignment with identical source operands */
446 int common_source = get_common_phi_source(ssa, phi);
447 if (common_source >= 0) {
448 zend_ssa_rename_var_uses(ssa, phi->ssa_var, common_source, 1);
449 zend_ssa_remove_phi(ssa, phi);
450 }
451 } else {
452 /* Pi assignment that is only used in Phi/Pi assignments */
453 // TODO What if we want to rerun type inference after DCE? Maybe separate this?
454 /*ZEND_ASSERT(phi->sources[0] != -1);
455 if (ssa->vars[phi->ssa_var].use_chain < 0) {
456 zend_ssa_rename_var_uses_keep_types(ssa, phi->ssa_var, phi->sources[0], 1);
457 zend_ssa_remove_phi(ssa, phi);
458 }*/
459 }
460 }
461
may_break_varargs(const zend_op_array * op_array,const zend_ssa * ssa,const zend_ssa_op * ssa_op)462 static inline zend_bool may_break_varargs(const zend_op_array *op_array, const zend_ssa *ssa, const zend_ssa_op *ssa_op) {
463 if (ssa_op->op1_def >= 0
464 && ssa->vars[ssa_op->op1_def].var < op_array->num_args) {
465 return 1;
466 }
467 if (ssa_op->op2_def >= 0
468 && ssa->vars[ssa_op->op2_def].var < op_array->num_args) {
469 return 1;
470 }
471 if (ssa_op->result_def >= 0
472 && ssa->vars[ssa_op->result_def].var < op_array->num_args) {
473 return 1;
474 }
475 return 0;
476 }
477
dce_live_ranges(context * ctx,zend_op_array * op_array,zend_ssa * ssa)478 static void dce_live_ranges(context *ctx, zend_op_array *op_array, zend_ssa *ssa)
479 {
480 int i = 0;
481 int j = 0;
482 zend_live_range *live_range = op_array->live_range;
483
484 while (i < op_array->last_live_range) {
485 if ((live_range->var & ZEND_LIVE_MASK) != ZEND_LIVE_TMPVAR) {
486 /* keep */
487 j++;
488 } else {
489 uint32_t var = live_range->var & ~ZEND_LIVE_MASK;
490 uint32_t def = live_range->start - 1;
491
492 if ((op_array->opcodes[def].result_type == IS_UNUSED) &&
493 (UNEXPECTED(op_array->opcodes[def].opcode == ZEND_EXT_STMT) ||
494 UNEXPECTED(op_array->opcodes[def].opcode == ZEND_EXT_FCALL_END) ||
495 UNEXPECTED(op_array->opcodes[def].opcode == ZEND_END_SILENCE))) {
496 def--;
497 }
498
499 if (op_array->opcodes[def].result_type == IS_UNUSED) {
500 if (op_array->opcodes[def].opcode == ZEND_DO_FCALL) {
501 /* constructor call */
502 do {
503 def--;
504 if ((op_array->opcodes[def].result_type & (IS_TMP_VAR|IS_VAR))
505 && op_array->opcodes[def].result.var == var) {
506 ZEND_ASSERT(op_array->opcodes[def].opcode == ZEND_NEW);
507 break;
508 }
509 } while (def > 0);
510 } else if (op_array->opcodes[def].opcode == ZEND_OP_DATA) {
511 def--;
512 }
513 }
514
515 #if ZEND_DEBUG
516 ZEND_ASSERT(op_array->opcodes[def].result_type & (IS_TMP_VAR|IS_VAR));
517 ZEND_ASSERT(op_array->opcodes[def].result.var == var);
518 ZEND_ASSERT(ssa->ops[def].result_def >= 0);
519 #else
520 if (!(op_array->opcodes[def].result_type & (IS_TMP_VAR|IS_VAR))
521 || op_array->opcodes[def].result.var != var
522 || ssa->ops[def].result_def < 0) {
523 /* TODO: Some wrong live-range? keep it. */
524 j++;
525 live_range++;
526 i++;
527 continue;
528 }
529 #endif
530
531 var = ssa->ops[def].result_def;
532
533 if ((ssa->var_info[var].type & (MAY_BE_STRING|MAY_BE_ARRAY|MAY_BE_OBJECT|MAY_BE_RESOURCE|MAY_BE_REF))
534 && !is_var_dead(ctx, var)) {
535 /* keep */
536 j++;
537 } else if (i != j) {
538 op_array->live_range[j] = *live_range;
539 }
540 }
541
542 live_range++;
543 i++;
544 }
545 op_array->last_live_range = j;
546 if (op_array->last_live_range == 0) {
547 efree(op_array->live_range);
548 op_array->live_range = NULL;
549 }
550 }
551
dce_optimize_op_array(zend_op_array * op_array,zend_ssa * ssa,zend_bool reorder_dtor_effects)552 int dce_optimize_op_array(zend_op_array *op_array, zend_ssa *ssa, zend_bool reorder_dtor_effects) {
553 int i;
554 zend_ssa_phi *phi;
555 int removed_ops = 0;
556
557 /* DCE of CV operations that changes arguments may affect vararg functions. */
558 zend_bool has_varargs = (ssa->cfg.flags & ZEND_FUNC_VARARG) != 0;
559
560 context ctx;
561 ctx.ssa = ssa;
562 ctx.op_array = op_array;
563 ctx.reorder_dtor_effects = reorder_dtor_effects;
564
565 /* We have no dedicated phi vector, so we use the whole ssa var vector instead */
566 ctx.instr_worklist_len = zend_bitset_len(op_array->last);
567 ctx.instr_worklist = alloca(sizeof(zend_ulong) * ctx.instr_worklist_len);
568 memset(ctx.instr_worklist, 0, sizeof(zend_ulong) * ctx.instr_worklist_len);
569 ctx.phi_worklist_len = zend_bitset_len(ssa->vars_count);
570 ctx.phi_worklist = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len);
571 memset(ctx.phi_worklist, 0, sizeof(zend_ulong) * ctx.phi_worklist_len);
572 ctx.phi_worklist_no_val = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len);
573 memset(ctx.phi_worklist_no_val, 0, sizeof(zend_ulong) * ctx.phi_worklist_len);
574
575 /* Optimistically assume all instructions and phis to be dead */
576 ctx.instr_dead = alloca(sizeof(zend_ulong) * ctx.instr_worklist_len);
577 memset(ctx.instr_dead, 0, sizeof(zend_ulong) * ctx.instr_worklist_len);
578 ctx.phi_dead = alloca(sizeof(zend_ulong) * ctx.phi_worklist_len);
579 memset(ctx.phi_dead, 0xff, sizeof(zend_ulong) * ctx.phi_worklist_len);
580
581 /* Mark reacable instruction without side effects as dead */
582 int b = ssa->cfg.blocks_count;
583 while (b > 0) {
584 int op_data = -1;
585
586 b--;
587 zend_basic_block *block = &ssa->cfg.blocks[b];
588 if (!(block->flags & ZEND_BB_REACHABLE)) {
589 continue;
590 }
591 i = block->start + block->len;
592 while (i > block->start) {
593 i--;
594
595 if (op_array->opcodes[i].opcode == ZEND_OP_DATA) {
596 op_data = i;
597 continue;
598 }
599
600 if (zend_bitset_in(ctx.instr_worklist, i)) {
601 zend_bitset_excl(ctx.instr_worklist, i);
602 add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], 0);
603 if (op_data >= 0) {
604 add_operands_to_worklists(&ctx, &op_array->opcodes[op_data], &ssa->ops[op_data], 0);
605 }
606 } else if (may_have_side_effects(op_array, ssa, &op_array->opcodes[i], &ssa->ops[i], ctx.reorder_dtor_effects)
607 || zend_may_throw(&op_array->opcodes[i], op_array, ssa)
608 || (has_varargs && may_break_varargs(op_array, ssa, &ssa->ops[i]))) {
609 if (op_array->opcodes[i].opcode == ZEND_NEW
610 && op_array->opcodes[i+1].opcode == ZEND_DO_FCALL
611 && ssa->ops[i].result_def >= 0
612 && ssa->vars[ssa->ops[i].result_def].escape_state == ESCAPE_STATE_NO_ESCAPE) {
613 zend_bitset_incl(ctx.instr_dead, i);
614 zend_bitset_incl(ctx.instr_dead, i+1);
615 } else {
616 add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], 0);
617 if (op_data >= 0) {
618 add_operands_to_worklists(&ctx, &op_array->opcodes[op_data], &ssa->ops[op_data], 0);
619 }
620 }
621 } else {
622 zend_bitset_incl(ctx.instr_dead, i);
623 if (op_data >= 0) {
624 zend_bitset_incl(ctx.instr_dead, op_data);
625 }
626 }
627 op_data = -1;
628 }
629 }
630
631 /* Propagate liveness backwards to all definitions of used vars */
632 while (!zend_bitset_empty(ctx.instr_worklist, ctx.instr_worklist_len)
633 || !zend_bitset_empty(ctx.phi_worklist, ctx.phi_worklist_len)) {
634 while ((i = zend_bitset_pop_first(ctx.instr_worklist, ctx.instr_worklist_len)) >= 0) {
635 zend_bitset_excl(ctx.instr_dead, i);
636 add_operands_to_worklists(&ctx, &op_array->opcodes[i], &ssa->ops[i], 1);
637 if (i < op_array->last && op_array->opcodes[i+1].opcode == ZEND_OP_DATA) {
638 zend_bitset_excl(ctx.instr_dead, i+1);
639 add_operands_to_worklists(&ctx, &op_array->opcodes[i+1], &ssa->ops[i+1], 1);
640 }
641 }
642 while ((i = zend_bitset_pop_first(ctx.phi_worklist, ctx.phi_worklist_len)) >= 0) {
643 zend_bitset_excl(ctx.phi_dead, i);
644 zend_bitset_excl(ctx.phi_worklist_no_val, i);
645 add_phi_sources_to_worklists(&ctx, ssa->vars[i].definition_phi, 1);
646 }
647 }
648
649 if (op_array->live_range) {
650 dce_live_ranges(&ctx, op_array, ssa);
651 }
652
653 /* Eliminate dead instructions */
654 ZEND_BITSET_FOREACH(ctx.instr_dead, ctx.instr_worklist_len, i) {
655 removed_ops += dce_instr(&ctx, &op_array->opcodes[i], &ssa->ops[i]);
656 } ZEND_BITSET_FOREACH_END();
657
658 /* Improper uses don't count as "uses" for the purpose of instruction elimination,
659 * but we have to retain phis defining them.
660 * Propagate this information backwards, marking any phi with an improperly used
661 * target as non-dead. */
662 while ((i = zend_bitset_pop_first(ctx.phi_worklist_no_val, ctx.phi_worklist_len)) >= 0) {
663 zend_ssa_phi *phi = ssa->vars[i].definition_phi;
664 int source;
665 zend_bitset_excl(ctx.phi_dead, i);
666 FOREACH_PHI_SOURCE(phi, source) {
667 add_to_phi_worklist_no_val(&ctx, source);
668 } FOREACH_PHI_SOURCE_END();
669 }
670
671 /* Now collect the actually dead phis */
672 FOREACH_PHI(phi) {
673 if (zend_bitset_in(ctx.phi_dead, phi->ssa_var)) {
674 zend_ssa_remove_uses_of_var(ssa, phi->ssa_var);
675 zend_ssa_remove_phi(ssa, phi);
676 } else {
677 /* Remove trivial phis (phis with identical source operands) */
678 try_remove_trivial_phi(&ctx, phi);
679 }
680 } FOREACH_PHI_END();
681
682 return removed_ops;
683 }
684
